<!doctype html>
<html style='font-size:18px !important'>
<head>
<meta charset='UTF-8'><meta name='viewport' content='width=device-width initial-scale=1'>
<title>背包问题</title><style type='text/css'>html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Courier",monospace; --title-bar-height:20px; }
.mac-os-11 { --title-bar-height:28px; }
html { font-size: 14px; background-color: var(--bg-color); color: var(--text-color); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; -webkit-font-smoothing: antialiased; }
body { margin: 0px; padding: 0px; height: auto; bottom: 0px; top: 0px; left: 0px; right: 0px; font-size: 1rem; line-height: 1.42857; overflow-x: hidden; background: inherit; tab-size: 4; }
iframe { margin: auto; }
a.url { word-break: break-all; }
a:active, a:hover { outline: 0px; }
.in-text-selection, ::selection { text-shadow: none; background: var(--select-text-bg-color); color: var(--select-text-font-color); }
#write { margin: 0px auto; height: auto; width: inherit; word-break: normal; overflow-wrap: break-word; position: relative; white-space: normal; overflow-x: visible; padding-top: 36px; }
#write.first-line-indent p { text-indent: 2em; }
#write.first-line-indent li p, #write.first-line-indent p * { text-indent: 0px; }
#write.first-line-indent li { margin-left: 2em; }
.for-image #write { padding-left: 8px; padding-right: 8px; }
body.typora-export { padding-left: 30px; padding-right: 30px; }
.typora-export .footnote-line, .typora-export li, .typora-export p { white-space: pre-wrap; }
.typora-export .task-list-item input { pointer-events: none; }
@media screen and (max-width: 500px) {
  body.typora-export { padding-left: 0px; padding-right: 0px; }
  #write { padding-left: 20px; padding-right: 20px; }
  .CodeMirror-sizer { margin-left: 0px !important; }
  .CodeMirror-gutters { display: none !important; }
}
#write li > figure:last-child { margin-bottom: 0.5rem; }
#write ol, #write ul { position: relative; }
img { max-width: 100%; vertical-align: middle; image-orientation: from-image; }
button, input, select, textarea { color: inherit; font: inherit; }
input[type="checkbox"], input[type="radio"] { line-height: normal; padding: 0px; }
*, ::after, ::before { box-sizing: border-box; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p, #write pre { width: inherit; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p { position: relative; }
p { line-height: inherit; }
h1, h2, h3, h4, h5, h6 { break-after: avoid-page; break-inside: avoid; orphans: 4; }
p { orphans: 4; }
h1 { font-size: 2rem; }
h2 { font-size: 1.8rem; }
h3 { font-size: 1.6rem; }
h4 { font-size: 1.4rem; }
h5 { font-size: 1.2rem; }
h6 { font-size: 1rem; }
.md-math-block, .md-rawblock, h1, h2, h3, h4, h5, h6, p { margin-top: 1rem; margin-bottom: 1rem; }
.hidden { display: none; }
.md-blockmeta { color: rgb(204, 204, 204); font-weight: 700; font-style: italic; }
a { cursor: pointer; }
sup.md-footnote { padding: 2px 4px; background-color: rgba(238, 238, 238, 0.7); color: rgb(85, 85, 85); border-radius: 4px; cursor: pointer; }
sup.md-footnote a, sup.md-footnote a:hover { color: inherit; text-transform: inherit; text-decoration: inherit; }
#write input[type="checkbox"] { cursor: pointer; width: inherit; height: inherit; }
figure { overflow-x: auto; margin: 1.2em 0px; max-width: calc(100% + 16px); padding: 0px; }
figure > table { margin: 0px; }
tr { break-inside: avoid; break-after: auto; }
thead { display: table-header-group; }
table { border-collapse: collapse; border-spacing: 0px; width: 100%; overflow: auto; break-inside: auto; text-align: left; }
table.md-table td { min-width: 32px; }
.CodeMirror-gutters { border-right: 0px; background-color: inherit; }
.CodeMirror-linenumber { user-select: none; }
.CodeMirror { text-align: left; }
.CodeMirror-placeholder { opacity: 0.3; }
.CodeMirror pre { padding: 0px 4px; }
.CodeMirror-lines { padding: 0px; }
div.hr:focus { cursor: none; }
#write pre { white-space: pre-wrap; }
#write.fences-no-line-wrapping pre { white-space: pre; }
#write pre.ty-contain-cm { white-space: normal; }
.CodeMirror-gutters { margin-right: 4px; }
.md-fences { font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; overflow: visible; white-space: pre; background: inherit; position: relative !important; }
.md-diagram-panel { width: 100%; margin-top: 10px; text-align: center; padding-top: 0px; padding-bottom: 8px; overflow-x: auto; }
#write .md-fences.mock-cm { white-space: pre-wrap; }
.md-fences.md-fences-with-lineno { padding-left: 0px; }
#write.fences-no-line-wrapping .md-fences.mock-cm { white-space: pre; overflow-x: auto; }
.md-fences.mock-cm.md-fences-with-lineno { padding-left: 8px; }
.CodeMirror-line, twitterwidget { break-inside: avoid; }
.footnotes { opacity: 0.8; font-size: 0.9rem; margin-top: 1em; margin-bottom: 1em; }
.footnotes + .footnotes { margin-top: 0px; }
.md-reset { margin: 0px; padding: 0px; border: 0px; outline: 0px; vertical-align: top; background: 0px 0px; text-decoration: none; text-shadow: none; float: none; position: static; width: auto; height: auto; white-space: nowrap; cursor: inherit; -webkit-tap-highlight-color: transparent; line-height: normal; font-weight: 400; text-align: left; box-sizing: content-box; direction: ltr; }
li div { padding-top: 0px; }
blockquote { margin: 1rem 0px; }
li .mathjax-block, li p { margin: 0.5rem 0px; }
li blockquote { margin: 1rem 0px; }
li { margin: 0px; position: relative; }
blockquote > :last-child { margin-bottom: 0px; }
blockquote > :first-child, li > :first-child { margin-top: 0px; }
.footnotes-area { color: rgb(136, 136, 136); margin-top: 0.714rem; padding-bottom: 0.143rem; white-space: normal; }
#write .footnote-line { white-space: pre-wrap; }
@media print {
  body, html { border: 1px solid transparent; height: 99%; break-after: avoid; break-before: avoid; font-variant-ligatures: no-common-ligatures; }
  #write { margin-top: 0px; padding-top: 0px; border-color: transparent !important; }
  .typora-export * { -webkit-print-color-adjust: exact; }
  .typora-export #write { break-after: avoid; }
  .typora-export #write::after { height: 0px; }
  .is-mac table { break-inside: avoid; }
}
.footnote-line { margin-top: 0.714em; font-size: 0.7em; }
a img, img a { cursor: pointer; }
pre.md-meta-block { font-size: 0.8rem; min-height: 0.8rem; white-space: pre-wrap; background: rgb(204, 204, 204); display: block; overflow-x: hidden; }
p > .md-image:only-child:not(.md-img-error) img, p > img:only-child { display: block; margin: auto; }
#write.first-line-indent p > .md-image:only-child:not(.md-img-error) img { left: -2em; position: relative; }
p > .md-image:only-child { display: inline-block; width: 100%; }
#write .MathJax_Display { margin: 0.8em 0px 0px; }
.md-math-block { width: 100%; }
.md-math-block:not(:empty)::after { display: none; }
.MathJax_ref { fill: currentcolor; }
[contenteditable="true"]:active, [contenteditable="true"]:focus, [contenteditable="false"]:active, [contenteditable="false"]:focus { outline: 0px; box-shadow: none; }
.md-task-list-item { position: relative; list-style-type: none; }
.task-list-item.md-task-list-item { padding-left: 0px; }
.md-task-list-item > input { position: absolute; top: 0px; left: 0px; margin-left: -1.2em; margin-top: calc(1em - 10px); border: none; }
.math { font-size: 1rem; }
.md-toc { min-height: 3.58rem; position: relative; font-size: 0.9rem; border-radius: 10px; }
.md-toc-content { position: relative; margin-left: 0px; }
.md-toc-content::after, .md-toc::after { display: none; }
.md-toc-item { display: block; color: rgb(65, 131, 196); }
.md-toc-item a { text-decoration: none; }
.md-toc-inner:hover { text-decoration: underline; }
.md-toc-inner { display: inline-block; cursor: pointer; }
.md-toc-h1 .md-toc-inner { margin-left: 0px; font-weight: 700; }
.md-toc-h2 .md-toc-inner { margin-left: 2em; }
.md-toc-h3 .md-toc-inner { margin-left: 4em; }
.md-toc-h4 .md-toc-inner { margin-left: 6em; }
.md-toc-h5 .md-toc-inner { margin-left: 8em; }
.md-toc-h6 .md-toc-inner { margin-left: 10em; }
@media screen and (max-width: 48em) {
  .md-toc-h3 .md-toc-inner { margin-left: 3.5em; }
  .md-toc-h4 .md-toc-inner { margin-left: 5em; }
  .md-toc-h5 .md-toc-inner { margin-left: 6.5em; }
  .md-toc-h6 .md-toc-inner { margin-left: 8em; }
}
a.md-toc-inner { font-size: inherit; font-style: inherit; font-weight: inherit; line-height: inherit; }
.footnote-line a:not(.reversefootnote) { color: inherit; }
.md-attr { display: none; }
.md-fn-count::after { content: "."; }
code, pre, samp, tt { font-family: var(--monospace); }
kbd { margin: 0px 0.1em; padding: 0.1em 0.6em; font-size: 0.8em; color: rgb(36, 39, 41); background: rgb(255, 255, 255); border: 1px solid rgb(173, 179, 185); border-radius: 3px; box-shadow: rgba(12, 13, 14, 0.2) 0px 1px 0px, rgb(255, 255, 255) 0px 0px 0px 2px inset; white-space: nowrap; vertical-align: middle; }
.md-comment { color: rgb(162, 127, 3); opacity: 0.8; font-family: var(--monospace); }
code { text-align: left; vertical-align: initial; }
a.md-print-anchor { white-space: pre !important; border-width: initial !important; border-style: none !important; border-color: initial !important; display: inline-block !important; position: absolute !important; width: 1px !important; right: 0px !important; outline: 0px !important; background: 0px 0px !important; text-decoration: initial !important; text-shadow: initial !important; }
.md-inline-math .MathJax_SVG .noError { display: none !important; }
.html-for-mac .inline-math-svg .MathJax_SVG { vertical-align: 0.2px; }
.md-math-block .MathJax_SVG_Display { text-align: center; margin: 0px; position: relative; text-indent: 0px; max-width: none; max-height: none; min-height: 0px; min-width: 100%; width: auto; overflow-y: hidden; display: block !important; }
.MathJax_SVG_Display, .md-inline-math .MathJax_SVG_Display { width: auto; margin: inherit; display: inline-block !important; }
.MathJax_SVG .MJX-monospace { font-family: var(--monospace); }
.MathJax_SVG .MJX-sans-serif { font-family: sans-serif; }
.MathJax_SVG { display: inline; font-style: normal; font-weight: 400; line-height: normal; zoom: 90%; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; }
.MathJax_SVG * { transition: none 0s ease 0s; }
.MathJax_SVG_Display svg { vertical-align: middle !important; margin-bottom: 0px !important; margin-top: 0px !important; }
.os-windows.monocolor-emoji .md-emoji { font-family: "Segoe UI Symbol", sans-serif; }
.md-diagram-panel > svg { max-width: 100%; }
[lang="flow"] svg, [lang="mermaid"] svg { max-width: 100%; height: auto; }
[lang="mermaid"] .node text { font-size: 1rem; }
table tr th { border-bottom: 0px; }
video { max-width: 100%; display: block; margin: 0px auto; }
iframe { max-width: 100%; width: 100%; border: none; }
.highlight td, .highlight tr { border: 0px; }
mark { background: rgb(255, 255, 0); color: rgb(0, 0, 0); }
.md-html-inline .md-plain, .md-html-inline strong, mark .md-inline-math, mark strong { color: inherit; }
mark .md-meta { color: rgb(0, 0, 0); opacity: 0.3 !important; }
@media print {
  .typora-export h1, .typora-export h2, .typora-export h3, .typora-export h4, .typora-export h5, .typora-export h6 { break-inside: avoid; }
}
.md-diagram-panel .messageText { stroke: none !important; }
.md-diagram-panel .start-state { fill: var(--node-fill); }
.md-diagram-panel .edgeLabel rect { opacity: 1 !important; }
.md-require-zoom-fix foreignobject { font-size: var(--mermaid-font-zoom); }


.CodeMirror { height: auto; }
.CodeMirror.cm-s-inner { background: inherit; }
.CodeMirror-scroll { overflow: auto hidden; z-index: 3; }
.CodeMirror-gutter-filler, .CodeMirror-scrollbar-filler { background-color: rgb(255, 255, 255); }
.CodeMirror-gutters { border-right: 1px solid rgb(221, 221, 221); background: inherit; white-space: nowrap; }
.CodeMirror-linenumber { padding: 0px 3px 0px 5px; text-align: right; color: rgb(153, 153, 153); }
.cm-s-inner .cm-keyword { color: rgb(119, 0, 136); }
.cm-s-inner .cm-atom, .cm-s-inner.cm-atom { color: rgb(34, 17, 153); }
.cm-s-inner .cm-number { color: rgb(17, 102, 68); }
.cm-s-inner .cm-def { color: rgb(0, 0, 255); }
.cm-s-inner .cm-variable { color: rgb(0, 0, 0); }
.cm-s-inner .cm-variable-2 { color: rgb(0, 85, 170); }
.cm-s-inner .cm-variable-3 { color: rgb(0, 136, 85); }
.cm-s-inner .cm-string { color: rgb(170, 17, 17); }
.cm-s-inner .cm-property { color: rgb(0, 0, 0); }
.cm-s-inner .cm-operator { color: rgb(152, 26, 26); }
.cm-s-inner .cm-comment, .cm-s-inner.cm-comment { color: rgb(170, 85, 0); }
.cm-s-inner .cm-string-2 { color: rgb(255, 85, 0); }
.cm-s-inner .cm-meta { color: rgb(85, 85, 85); }
.cm-s-inner .cm-qualifier { color: rgb(85, 85, 85); }
.cm-s-inner .cm-builtin { color: rgb(51, 0, 170); }
.cm-s-inner .cm-bracket { color: rgb(153, 153, 119); }
.cm-s-inner .cm-tag { color: rgb(17, 119, 0); }
.cm-s-inner .cm-attribute { color: rgb(0, 0, 204); }
.cm-s-inner .cm-header, .cm-s-inner.cm-header { color: rgb(0, 0, 255); }
.cm-s-inner .cm-quote, .cm-s-inner.cm-quote { color: rgb(0, 153, 0); }
.cm-s-inner .cm-hr, .cm-s-inner.cm-hr { color: rgb(153, 153, 153); }
.cm-s-inner .cm-link, .cm-s-inner.cm-link { color: rgb(0, 0, 204); }
.cm-negative { color: rgb(221, 68, 68); }
.cm-positive { color: rgb(34, 153, 34); }
.cm-header, .cm-strong { font-weight: 700; }
.cm-del { text-decoration: line-through; }
.cm-em { font-style: italic; }
.cm-link { text-decoration: underline; }
.cm-error { color: red; }
.cm-invalidchar { color: red; }
.cm-constant { color: rgb(38, 139, 210); }
.cm-defined { color: rgb(181, 137, 0); }
div.CodeMirror span.CodeMirror-matchingbracket { color: rgb(0, 255, 0); }
div.CodeMirror span.CodeMirror-nonmatchingbracket { color: rgb(255, 34, 34); }
.cm-s-inner .CodeMirror-activeline-background { background: inherit; }
.CodeMirror { position: relative; overflow: hidden; }
.CodeMirror-scroll { height: 100%; outline: 0px; position: relative; box-sizing: content-box; background: inherit; }
.CodeMirror-sizer { position: relative; }
.CodeMirror-gutter-filler, .CodeMirror-hscrollbar, .CodeMirror-scrollbar-filler, .CodeMirror-vscrollbar { position: absolute; z-index: 6; display: none; }
.CodeMirror-vscrollbar { right: 0px; top: 0px; overflow: hidden; }
.CodeMirror-hscrollbar { bottom: 0px; left: 0px; overflow: hidden; }
.CodeMirror-scrollbar-filler { right: 0px; bottom: 0px; }
.CodeMirror-gutter-filler { left: 0px; bottom: 0px; }
.CodeMirror-gutters { position: absolute; left: 0px; top: 0px; padding-bottom: 30px; z-index: 3; }
.CodeMirror-gutter { white-space: normal; height: 100%; box-sizing: content-box; padding-bottom: 30px; margin-bottom: -32px; display: inline-block; }
.CodeMirror-gutter-wrapper { position: absolute; z-index: 4; background: 0px 0px !important; border: none !important; }
.CodeMirror-gutter-background { position: absolute; top: 0px; bottom: 0px; z-index: 4; }
.CodeMirror-gutter-elt { position: absolute; cursor: default; z-index: 4; }
.CodeMirror-lines { cursor: text; }
.CodeMirror pre { border-radius: 0px; border-width: 0px; background: 0px 0px; font-family: inherit; font-size: inherit; margin: 0px; white-space: pre; overflow-wrap: normal; color: inherit; z-index: 2; position: relative; overflow: visible; }
.CodeMirror-wrap pre { overflow-wrap: break-word; white-space: pre-wrap; word-break: normal; }
.CodeMirror-code pre { border-right: 30px solid transparent; width: fit-content; }
.CodeMirror-wrap .CodeMirror-code pre { border-right: none; width: auto; }
.CodeMirror-linebackground { position: absolute; left: 0px; right: 0px; top: 0px; bottom: 0px; z-index: 0; }
.CodeMirror-linewidget { position: relative; z-index: 2; overflow: auto; }
.CodeMirror-wrap .CodeMirror-scroll { overflow-x: hidden; }
.CodeMirror-measure { position: absolute; width: 100%; height: 0px; overflow: hidden; visibility: hidden; }
.CodeMirror-measure pre { position: static; }
.CodeMirror div.CodeMirror-cursor { position: absolute; visibility: hidden; border-right: none; width: 0px; }
.CodeMirror div.CodeMirror-cursor { visibility: hidden; }
.CodeMirror-focused div.CodeMirror-cursor { visibility: inherit; }
.cm-searching { background: rgba(255, 255, 0, 0.4); }
@media print {
  .CodeMirror div.CodeMirror-cursor { visibility: hidden; }
}


@import '';

/*by H16nning*/

:root {
  --bg-color: white;
  --side-bar-bg-color: #f5f7f9;
  --control-text-color: #3b454e;
  --primary-color: rgb(56, 132, 255);
  --primary-btn-border-color: rgb(56, 132, 255);
  --active-file-bg-color: #e6ecf1;
  --active-file-text-color: inherit;
  --active-file-border-color: rgb(56, 132, 255);
  --item-hover-text-color: #242a31;
  --item-hover-bg-color: #f5f7f9;
  --window-border: 1px solid #e6ecf1;
  --select-text-font-color: white;
  --select-text-bg-color: #3277e5;

  --md-char-color: #9daab6;
  --heading-char-color: #9daab6;
  --meta-content-color: rgb(56, 132, 255);

  --borders: #e6ecf1;
  --table-border-color: #e6ecf1;
  --boxes: #f5f7f9;
  --boxes-darker: #d8e0e7;
  --boxes-darker2: #bac2c9;
  --boxes-darkest: #9daab6;
  --drag-placeholder-color: #d8e0e7;

  --mds: #183055;
  --text-color: #3b454e;
  --heading-text-color: #242a31;
  --light-text-color: #9daab6;
  --light-text-color-darker: #74818d;
  --codeboxes: #183055;
  --rawblock-edit-panel-bd: transparent;

  --primary-color-white: #82abec;
  --primary-color-white-darker: #5a83c5;
  --primary-color-darker: #2f6dd1;
  --focus-ring-color: rgb(56, 132, 255);

  --danger-color: rgb(255, 70, 66);

  --node-fill: #ececff;
  --node-border: #ccccff;
  --cluster-fill: #ffffde;
  --cluster-border: #aaaa33;
  --note-fill: #fff5ad;
  --note-border: #aaaa33;

  /*****************************/

  --font-family: 'JetBrains Mono', sans-serif;
  --code-font-family: 'JetBrains Mono';
  --monospace: 'JetBrains Mono';
}

html,
.form-control,
.modal {
  font-size: 16px;
}

body {
  background: var(--bg-color);
  font-family: var(--font-family);
  font-weight: 400;
  color: #3b454e;
  line-height: 1.600rem;
  height: 100%;
}

#write {
  max-width: 870px;
  margin: 0 auto;
  padding: 30px;
  padding-bottom: 100px;
  position: static;
  width: 100%;
}

#write > ul:first-child,
#write > ol:first-child {
  margin-top: 30px;
}

a {
  color: var(--primary-color);
  text-decoration: none !important;
  transition-duration: 0.2s;
  transition-property: color;
}

a:hover {
  color: var(--primary-color-darker);
}

.ty-preferences a {
  color: var(--primary-color);
}

h1,
h2,
h3,
h4,
h5,
h6 {
  position: relative;
  color: var(--heading-text-color);
  cursor: text;
}

h1:hover a.anchor,
h2:hover a.anchor,
h3:hover a.anchor,
h4:hover a.anchor,
h5:hover a.anchor,
h6:hover a.anchor {
  text-decoration: none;
}

h1 tt,
h1 code {
  font-size: inherit;
}

h2 tt,
h2 code {
  font-size: inherit;
}

h3 tt,
h3 code {
  font-size: inherit;
}

h4 tt,
h4 code {
  font-size: inherit;
}

h5 tt,
h5 code {
  font-size: inherit;
}

h6 tt,
h6 code {
  font-size: inherit;
}

h1 {
  font-size: 2rem;
  font-weight: 500;
  line-height: 1.5;
  margin-top: 3rem;
  margin-bottom: 1rem;
  padding-bottom: 0.4rem;
  border-bottom: solid 2px var(--borders);
}

h2 {
  font-size: 1.6rem;
  font-weight: 700;
  line-height: 1.5;
  margin-top: 2.25rem;
  margin-bottom: 0.5rem;
}

h3 {
  font-size: 1.4rem;
  font-weight: 700;
  line-height: 1.5;
  margin-top: 2rem;
  margin-bottom: 0.5rem;
}

h4 {
  font-size: 1.2rem;
  font-weight: 700;
  line-height: 1.5;
  margin-top: 1.75rem;
  margin-bottom: 0.5rem;
}

h5 {
  font-size: 1rem;
  font-weight: 700;
  line-height: 1.5;
  margin-top: 1.5rem;
  margin-bottom: 0.5rem;
}

h6 {
  font-size: 1rem;
  font-weight: 700;
  line-height: 1.5;
  margin-top: 1.5rem;
  margin-bottom: 0.5rem;
  opacity: 0.8;
}

#write > h1.md-focus:before,
#write > h2.md-focus:before,
#write > h3.md-focus:before,
#write > h4.md-focus:before,
#write > h5.md-focus:before,
#write > h6.md-focus:before {
  color: var(--light-text-color);
  border: none;
  position: absolute;
  font-size: 1rem;
  font-weight: 700;
  padding: 0px;
  line-height: 1;
}

#write > h1.md-focus:before {
  content: 'h1';
  top: 1.25rem;
  left: -1.75rem;
}

#write > h2.md-focus:before {
  content: 'h2';
  top: 0.8rem;
  left: -1.75rem;
}

#write > h3.md-focus:before {
  content: 'h3';
  top: 0.55rem;
  left: -1.75rem;
}

#write > h4.md-focus:before {
  content: 'h4';
  top: 0.35rem;
  left: -1.75rem;
}

#write > h5.md-focus:before {
  content: 'h5';
  top: 0.2rem;
  left: -1.75rem;
}

#write > h6.md-focus:before {
  content: 'h6';
  top: 0.2rem;
  left: -1.75rem;
}

h1:first-child,
h2:first-child,
h3:first-child,
h4:first-child,
h5:first-child,
h6:first-child,
blockquote h1,
blockquote h2,
blockquote h3,
blockquote h4,
blockquote h5,
blockquote h6 {
  margin-top: 0rem;
}

p,
blockquote,
ul,
ol,
dl {
  margin: 0.5rem 0rem 1.5rem 0rem;
}

li > ol,
li > ul {
  margin: 0 0;
}

hr {
  height: 2px;
  padding: 0;
  margin: 16px 0;
  background-color: var(--borders);
  border: 0 none;
  overflow: hidden;
  box-sizing: content-box;
}

li p.first {
  display: inline-block;
}

ul,
ol {
  padding-left: 30px;
}

ul:first-child,
ol:first-child {
  margin-top: 0;
}

ul:last-child,
ol:last-child {
  margin-bottom: 0;
}

.md-blockmeta {
  color: var(--md-char-color);
}

mark {
  background-color: hsla(217, 100%, 50%, 0.2);
  color: var(--text-color);
}

/*BLOCKQUOTE*/

blockquote {
  width: 100%;
  background-color: rgba(220, 230, 255, 0.32);
  border-left: 4px solid rgb(56, 97, 255);
  border-radius: 0.5rem;
  padding: 0.8rem;
}
p, blockquote, ul, ol, dl {
  margin: 0.8rem 0rem 0.5rem 0rem;
}

blockquote blockquote {
  padding-right: 0;
}

/*TABLE*/

table {
  font-size: 0.875rem;
  padding: 0;
  margin: 1.5rem 0;
  word-break: initial;
}

table tr {
  border-top: 1px solid var(--borders);
  border-bottom: 1px solid var(--borders);
  margin: 0;
  padding: 0;
}

table tr.md-end-block {
  border-top: none;
}

table tr th {
  font-weight: bold;
  border: none;
  border-bottom: solid 2px var(--borders);
  margin: 0;
  padding: 10px 16px;
  transition-duration: 0.3s;
  transition-property: background-color;
}

table tr td {
  border: none;
  margin: 0;
  padding: 10px 16px;
  transition-duration: 0.3s;
  transition-property: background-color;
}

#write table tr td:hover,
#write table tr th:hover {
  background-color: var(--boxes);
}

table tr th:first-child,
table tr td:first-child {
  margin-top: 0;
}

table tr th:last-child,
table tr td:last-child {
  margin-bottom: 0;
}

/*OTHER TABLE THINGS*/

.ty-table-edit {
  padding: 0.3rem;
  border: solid 1px var(--borders);
  border-radius: 0.3rem;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
  transition-duration: 0.3s;
  transition-property: opacity;
}

.ty-table-edit:active,
.ty-table-edit:focus,
.popover:active,
.popover:focus {
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

.popover {
  border: solid 1px var(--borders);
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
  border-radius: 0.3rem;
}

.popover .arrow {
  border-bottom-color: var(--borders);
}

.md-grid-board .md-grid-ext {
  background-color: var(--boxes);
}

.md-grid-board tr[row='1'] .md-grid-ext {
  background-color: var(--boxes-darkest);
}

.md-grid-board a.md-active,
.md-grid-board a:hover {
  background-color: var(--primary-color-white);
  border-color: var(--primary-color-white-darker);
}

#md-grid-width,
#md-grid-height {
  border-radius: 0.3rem;
  border-color: var(--borders);
}

#md-grid-width,
#md-grid-height {
  border-radius: 0.3rem;
  border-color: var(--borders);
  transition-duration: 0.3s;
  transition-property: border-color;
}

#md-grid-width:focus,
#md-grid-height:focus {
  border-radius: 0.3rem;
  border-color: var(--primary-color);
}

/*CODE*/

.CodeMirror {
  padding: 0.5rem;
  font-family: 'Consolas', monospace;
}

.cm-s-inner .CodeMirror-gutters {
  background-color: none;
  border-right: none;
  border-radius: 0px;
  width: 2rem;
  color: white;
  height: 100%;
  white-space: nowrap;
}

.cm-s-inner .CodeMirror-gutter-wrapper {
  left: -2.75rem !important;
}

.CodeMirror.cm-s-typora-default div.CodeMirror-cursor {
  border-left: solid 2px var(--light-text-color-darker);
}

.CodeMirror.cm-s-typora-default .CodeMirror-activeline-background {
  background-color: var(--boxes);
}

.cm-s-inner .CodeMirror-cursor {
  color: black;
  border-left: solid 1px black;
}

.cm-s-inner .CodeMirror-linenumber {
  color: var(--bg-color);
  opacity: 0.6;
  width: 1.9532rem !important /*required*/;
}

.cm-s-inner .CodeMirror-line::selection,
.cm-s-inner .CodeMirror-line::-moz-selection,
.cm-s-inner .CodeMirror-line > span::selection,
.cm-s-inner .CodeMirror-line > span::-moz-selection,
.cm-s-inner .CodeMirror-line > span > span::selection,
.cm-s-inner .CodeMirror-line > span > span::-moz-selection {
  background-color: rgba(255, 255, 255, 0.1);
}

.cm-s-inner span.cm-comment {
  color: #9daab6;
}

.cm-s-inner span.cm-string,
.cm-s-inner span.cm-string-2 {
  color: #71a7ff;
}

.cm-s-inner span.cm-number {
  color: #ff9d3d;
}

.cm-s-inner span.cm-variable,
.cm-s-inner span.cm-variable-2 {
  color: white;
}

.cm-s-inner span.cm-def {
  color: white;
}

.cm-s-inner span.cm-operator {
  color: #ff9d3d;
}

.cm-s-inner span.cm-keyword {
  color: #61e3a5;
}

.cm-s-inner span.cm-atom {
  color: #bd93f9;
}

.cm-s-inner span.cm-meta {
  color: #f8f8f2;
}

.cm-s-inner span.cm-link {
  color: var(--primary-color);
}

.cm-s-inner span.cm-tag,
.cm-s-inner .cm-header {
  color: #b4f6d6;
}

.cm-s-inner span.cm-attribute {
  color: #ff9d3d;
}

.cm-s-inner span.cm-qualifier,
.cm-s-inner span.cm-type,
.cm-s-inner span.cm-variable-3 {
  color: #82ee9d;
}

.cm-s-inner span.cm-property {
  color: #ffd6ad;
}

.cm-s-inner span.cm-builtin {
  color: #8ffaaa;
}

.md-fences.md-focus .cm-s-inner .CodeMirror-activeline-background {
  background: none;
}

.cm-s-inner .CodeMirror-selected,
.cm-s-inner .CodeMirror-selectedtext {
  background-color: rgba(255, 255, 255, 0.1);
}

.cm-s-typora-default .cm-header,
.cm-s-typora-default .cm-property {
  color: var(--primary-color);
}

#typora-source span.cm-variable {
  color: var(--window-border);
}

#typora-source span.cm-def {
  color: var(--text-color);
}

#write .code-tooltip {
  box-shadow: rgba(116, 129, 141, 0.08) 0px 2px 6px 0px;
  border: solid 1px var(--borders);
  border-radius: 0.3rem;
  background-color: var(--bg-color);
  color: var(--text-color);
  width: 15rem;
  height: 2.5rem;
  bottom: -3rem;
  padding: 0.1875rem;
}

#write .code-tooltip .ty-input {
  border: solid 1px var(--borders);
  height: 2rem;
  line-height: 2rem;
  margin: 0rem;
  padding-left: 0.5rem !important;
  text-align: left;
  display: block;
  font-size: 0.9rem;
  font-weight: 600;
  font-family: var(--font-family);
  transition-duration: 0.3s;
  transition-property: border;
}

#write .code-tooltip .ty-input:focus {
  border-color: var(--primary-color);
}

.html-for-mac .ty-cm-lang-input:empty:after {
  left: 0.5rem;
}

.autoComplt-list li,
.fences-auto-suggest li {
  font-weight: 500;
  transition-duration: 0.3s;
  transition-property: background-color, color;
}

.autoComplt-list li.active,
.fences-auto-suggest li:hover {
  background-color: var(--boxes);
  color: var(--primary-color);
}

.md-fences,
tt {
  border-radius: 0.3rem;
  color: #ffffff;
  padding: 1.5rem;
  font-size: 0.9rem;
}

code {
	padding: 0.2rem 0.4rem;
	background-color: rgb(235, 243, 255);
	font-size: 0.975rem;
	border-radius: 0.2rem;
	margin: 0.2rem;
}



.md-fences .CodeMirror div.CodeMirror-cursor {
  border-left: solid 1px white;
}

.md-fences {
  margin-bottom: 1.3rem;
  margin-top: 1.3rem;
  padding-top: 8px;
  padding-bottom: 8px;
  background-color: rgb(24,48,85);
}

/*DIAGRAMS*/

.md-diagram-panel {
  color: var(--text-color);
  border: solid 1px var(--borders);
  border-radius: 0.3rem;
}

.md-diagram-panel text,
.md-diagram-panel .label {
  color: var(--text-color);
}

.md-diagram-panel text {
  fill: var(--text-color) !important /*required*/;
}

.md-diagram-panel-error {
  color: var(--danger-color);
}

/*CHECKBOXES*/

.md-task-list-item > input:before,
input[type='checkbox']:before {
  border-radius: 0.2rem;
  margin-top: -0.08rem;
  margin-left: -0.1rem;
  width: 1rem;
  height: 1rem;
  background-color: var(--borders);
  content: ' ';
  display: block;
  transition-duration: 0.3s;
  transition-property: background-color;
}

.md-task-list-item:hover > input:before,
input[type='checkbox']:hover:before {
  background-color: var(--boxes-darker);
}

.md-task-list-item > input:checked:before,
.md-task-list-item > input[checked]:before,
input[type='checkbox']:checked:before {
  background-color: var(--primary-color);
}

.md-task-list-item:hover > input:checked:before,
.md-task-list-item:hover > input[checked]:before,
input[type='checkbox']:hover:checked:before {
  background-color: var(--primary-color-darker);
}

.md-task-list-item > input:after,
.md-task-list-item > input:after,
input[type='checkbox']:after {
  transform: rotate(-45deg);
  position: absolute;
  border: 2px solid white;
  border-top: 0;
  border-right: 0;
  top: 0.16rem;
  left: 0.1rem;
  width: 0.6rem;
  height: 0.375rem;
  content: ' ';
  opacity: 0;
  transition-duration: 0.3s;
  transition-property: opacity;
}

.md-task-list-item > input:checked:after,
.md-task-list-item > input[checked]:after,
input[type='checkbox']:checked:after {
  opacity: 1;
}

.ty-preferences input[type='checkbox']:before {
  width: 1.2rem;
  height: 1.2rem;
}

.ty-preferences input[type='checkbox']:after {
  width: 0.5rem;
  height: 0.32rem;
  top: 0.19rem;
  left: 0.14rem;
}

@media print {
  html {
    font-size: 13px;
  }

  table,
  pre {
    page-break-inside: avoid;
  }

  pre {
    word-wrap: break-word;
  }
}

#write pre.md-meta-block {
  padding: 1rem;
  line-height: 1.45;
  background-color: var(--boxes);
  border: 0;
  border-radius: 0.3rem;
  color: var(--text-color);
  border-left: solid 4px var(--boxes-darkest);
}

.md-image > .md-meta {
  border-radius: 3px;
  padding: 2px 0px 0px 4px;
  font-size: 0.9em;
  color: inherit;
}

.md-tag {
  color: var(--md-char-color);
  opacity: 1;
}

/*TOC*/

.md-toc {
  margin: 1.5rem 0rem;
}

.md-toc:focus .md-toc-content {
  border: none;
}

.md-toc-tooltip .btn {
  padding: 0.5rem;
  line-height: 1rem;
}

.md-toc-tooltip .btn:hover {
  color: var(--primary-color) !important /*required*/;
  background-color: var(--boxes) !important /*required*/;
}

/*MATH*/

.MathJax_SVG:focus {
  outline: none;
}

.md-rawblock {
  margin: 1.5rem 0rem;
}

.md-rawblock-container {
  transition-duration: 0.3s;
  transition-property: box-shadow, border;
  padding: 8px;
  border: solid 1px transparent;
  border-radius: 0.3rem;
}

.md-rawblock:hover > .md-rawblock-container {
  background-color: transparent;
  border: solid 1px var(--borders);
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

.md-math-block .md-rawblock-control:not(.md-rawblock-tooltip) {
  background-color: var(--bg-color);
  border-left: solid 2px var(--primary-color);
  border-right: solid 2px var(--primary-color);
}

.md-math-block .md-rawblock-before {
  border-top-left-radius: 0.3rem;
  border-top-right-radius: 0.3rem;
  border-top: solid 2px var(--primary-color);
}

.md-math-block .md-rawblock-after {
  border-bottom-left-radius: 0.3rem;
  border-bottom-right-radius: 0.3rem;
  border-bottom: solid 2px var(--primary-color);
  margin-bottom: 0.5rem;
}

#write .md-math-block .code-tooltip {
  width: 100%;
}

.md-mathblock-input span.cm-tag {
  color: #15726d;
}

.md-mathblock-input span.cm-atom {
  color: #8a1fa0;
}

.md-mathblock-input span.cm-number {
  color: #df4617;
}

/*HTML*/

.md-htmlblock-panel {
  border: solid 2px var(--primary-color);
  border-radius: 0.3rem;
}

/*FOOTER*/

footer.ty-footer {
  border: none;
}

.footer-item {
  opacity: 1 !important;
  color: var(--light-text-color);
  transition: 0.3s;
}

.footer-item:hover {
  color: var(--light-text-color-darker) !important;
}

#outline-btn:hover {
  color: var(--light-text-color-darker) !important;
}

/*SIDEBAR*/

#typora-sidebar {
  border-right: solid 1px var(--borders);
}

.info-panel-tab {
  opacity: 1;
}

.info-panel-tab-border {
  color: var(--primary-color);
  border-radius: 2px;
}

#ty-sidebar-search-back-btn {
  margin: auto;
}

.ty-show-outline-filter #file-library-search,
.ty-show-search #file-library-search {
  height: 4rem;
}

#file-library-search-input {
  height: 2rem;
}

#file-library-search-panel input {
  margin-top: 8px !important;
}

.ty-sidebar-search-panel .searchpanel-search-option-btn {
  top: 14px;
}

#typora-sidebar #filesearch-case-ion-btn,
#typora-sidebar #filesearch-word-ion-btn {
  background: none;
  margin-top: 0.45rem;
  transition-duration: 0.2s;
  transition-property: background-color;
}

#typora-sidebar #filesearch-case-ion-btn:hover,
#typora-sidebar #filesearch-word-ion-btn:hover {
  color: var(--primary-color);
}

/*sidebar outline*/

#close-outline-filter-btn {
  top: 15px;
  opacity: 1;
  color: var(--light-text-color) !important;
}

#close-outline-filter-btn:hover {
  color: var(--primary-color) !important;
  background-color: transparent !important;
}

#close-outline-filter-btn:active {
  background-color: transparent !important;
}

#outline-content {
  padding-right: 0px;
  line-height: 1rem;
}

.outline-item {
  display: flex;
  padding-top: 0px;
  padding-bottom: 0px;
}

.outline-item .outline-label {
  display: block;
  width: 100%;
  padding-top: 0.4rem;
  padding-bottom: 0.4rem;
  border-right: solid 2px transparent;
  font-size: 0.8rem;
  font-weight: 500;
  color: var(--light-text-color-darker);
  transition-duration: 0.3s;
  transition-property: color;
}

.outline-item:hover {
  background: none;
}

.outline-item:hover .outline-label {
  color: var(--primary-color);
}

.outline-label:hover {
  text-decoration: none;
}

.outline-active.outline-label {
  border-right: solid 2px var(--primary-color);
  font-weight: 500;
  color: var(--primary-color);
}

.outline-expander {
  padding-top: 0.4rem;
  padding-right: 0.5rem;
}

/*sidebar file-list and search results*/

#file-library-list[data-state='complete'] #sidebar-loading-template {
  padding: 0rem;
}

#typora-sidebar .file-list-item,
.ty-search-item {
  border: none;
  transition-duration: 0.3s !important;
  transition-property: background-color, border, color, height !important;
  padding: 1rem;
}

#typora-sidebar .file-list-item:hover,
.ty-search-item:hover {
  background: var(--borders);
}

#typora-sidebar .ty-search-item-line:hover,
#typora-sidebar .ty-search-item-line.active {
  background-color: transparent;
}

#typora-sidebar .ty-search-item-line.active {
  color: var(--primary-color);
  font-weight: 800;
}

#typora-sidebar .file-list-item-file-name {
  font-weight: 800;
  font-size: 0.9rem;
  margin-bottom: 0rem;
  line-height: 1.8rem;
  float: right;
}

#typora-sidebar .file-list-item-file-ext-part {
  font-weight: 800;
  opacity: 0.5;
}

#typora-sidebar .file-list-item-parent-loc,
#typora-sidebar .file-list-item-time {
  font-weight: 400;
  opacity: 0.5;
  display: block;
}

#typora-sidebar .file-list-item-summary {
  float: left;
  font-size: 0.8rem;
  opacity: 0.9;
}

#typora-sidebar input.file-list-item-file-name {
  margin: 0.5rem 0rem 0.5rem 0.7rem;
  padding: 0.4rem !important;
  line-height: 1rem;
  float: right;
  border-radius: 0.3rem;
  font-weight: 500;
  background-color: white !important;
}

#typora-sidebar .file-list-item.file-library-file-node {
  border: none;
}

#typora-sidebar .file-tree-node.active .file-node-background,
#typora-sidebar .file-list-item.active,
#typora-sidebar .ty-search-item.active {
  background-color: white;
  outline: 1px solid var(--borders);
  border: none;
  color: var(--primary-color) !important;
}

#typora-sidebar .file-tree-node.active .file-node-content {
  color: var(--primary-color) !important;
}

#typora-sidebar .file-tree-node {
  padding: 0rem;
  font-weight: 500;
  font-size: 0.9rem;
  margin-left: 0.8rem;
}

#typora-sidebar .file-tree-node .file-node-content {
  padding: 0rem;
  line-height: 2.2rem;
  height: 2.2rem;
  background: none;
}

#typora-sidebar .file-tree-node .file-node-background {
  padding: 0rem;
  height: 2.2rem;
}

#typora-sidebar .file-tree-node .file-node-icon {
  margin-right: 0.5rem;
}

#typora-sidebar .file-tree-node .file-node-icon.fa-file-text-o {
  margin-top: 0.33rem;
}

#typora-sidebar .file-tree-node .file-node-icon.fa-folder {
  margin-top: 0.36rem;
}

#typora-sidebar .file-tree-node .fa-caret-down,
#typora-sidebar .file-tree-node .fa-caret-right {
  position: relative;
  top: 5px;
}

#typora-sidebar .file-tree-node .file-tree-rename-input {
  height: 2.2rem;
  background: none;
  border: none;
  font-size: 0.9rem;
  font-weight: 500;
  margin: 0rem;
  padding-left: 0rem;
}

#typora-sidebar .ty-search-item-collapse-icon {
  top: 9px;
}

/*no left border*/
#typora-sidebar .file-tree-node.active > .file-node-background {
  border: none;
}

/*no dotted highlighting*/
.file-library-node:not(.file-node-root):focus > .file-node-content {
  outline: none;
}

#typora-sidebar #sidebar-files-menu {
  border: solid 1px var(--borders);
  border-radius: 0.3rem;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

#typora-sidebar #ty-sidebar-footer {
  background-color: var(--bg-color);
  border-top: solid 1px var(--borders);
  font-weight: 500;
}

#typora-sidebar #ty-sidebar-footer li {
  transition-duration: 0.2s;
  transition-property: background-color, color;
}

#typora-sidebar #ty-sidebar-footer li:hover {
  color: var(--primary-color);
  background-color: var(--boxes);
}

/*cursor*/
.file-node-content:hover {
  cursor: pointer;
}

.file-tree-node:not(.file-node-root):not(.file-node-expanded) .file-node-background {
  transition-duration: 0.2s;
  transition-property: background-color;
}

.file-tree-node:not(.file-node-root):not(.file-node-expanded):hover .file-node-background {
  background-color: var(--borders);
}

#typora-sidebar .sidebar-footer-item {
  transition-duration: 0.2s;
  transition-property: background-color, color;
  font-weight: 700;
}

#typora-sidebar .sidebar-footer-item:hover {
  color: var(--primary-color);
  background-color: var(--boxes);
}

#typora-quick-open {
  background-color: white;
  border: 1px solid var(--borders);
  border-radius: 0.3rem;
  padding: 0rem;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

#typora-quick-open-input {
  margin-right: 20px;
}

#typora-quick-open-input .input {
  box-shadow: none;
  border: none;
  margin: 0.5rem;
  margin-left: 0.8rem;
}

.typora-quick-open-item {
  background-color: white;
  border: none;
  font-weight: 500;
  transition-duration: 0.2s;
  transition-property: background-color;
}

.typora-quick-open-item:hover {
  background-color: var(--boxes);
  color: var(--primary-color);
}

.typora-quick-open-item.active {
  background-color: var(--boxes);
  border: none;
}

.ty-quick-open-category-title {
  font-size: 10px;
  font-weight: 700;
  letter-spacing: 1.2px;
  text-transform: uppercase;
  opacity: 1;
  color: var(--light-text-color);
  line-height: 32px;
  padding-top: 6px;
  height: 32px;
}

/** focus mode */
.on-focus-mode blockquote {
  border-left-color: rgba(85, 85, 85, 0.12);
}

.md-lang {
  color: var(--primary-color);
}

/*NOTIFICATION*/

#md-notification {
  border-bottom: solid 1px var(--borders);
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

#md-notifcation .btn {
  border: 0;
}

/*PREFERENCES*/

.ty-preferences {
  font-family: var(--font-family);
}

.ty-preferences .window-header {
  justify-content: space-between;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
  border-bottom: solid 1px var(--borders);
}

.ty-preferences .window-header-content {
  background-color: white;
  margin: 0rem;
}

.ty-preferences .window-header h2 {
  font-weight: 600;
  font-size: 1.5rem;
  margin: 0rem;
  margin-left: 1rem;
}

.unibody-window .ty-preferences .window-header h2 {
  margin-left: 1rem !important;
}

.ty-preferences .window-header-back {
  margin-left: 1.2rem;
}

.ty-preferences .window-header-back .icon {
  border-right: none;
}

/*preferences sidebar*/
.ty-preferences .window-content {
  background-color: white;
}

.ty-preferences .nav-group-item {
  color: var(--text-color);
  height: 2.5rem;
  line-height: 2.6rem;
  font-weight: 500;
  padding: 0px 0px 0px 2rem;
  font-size: 1rem;
  transition-duration: 0.2s;
  transition-property: background-color;
}

.ty-preferences .nav-group-item:hover {
  background-color: var(--borders);
  border-radius: 0px;
}

.ty-preferences .nav-group-item.active {
  border-radius: 0rem;
  border: none;
  outline: 1px solid var(--borders);
  background-color: white;
  color: var(--primary-color);
}

.ty-preferences .pane-sm {
  background: var(--boxes);
  flex-basis: 240px;
  flex-grow: 0;
  justify-content: center;
  border-right: 1px solid var(--borders);
  margin: 0rem;
  padding: 0rem;
}

.ty-preferences .pane-sm .list-group {
  width: 100%;
  max-width: 30rem;
}

.ty-preferences .list-group-header {
  display: flex;
  justify-content: space-around;
}

.ty-preferences .list-group-header div {
  width: 100%;
  margin-right: 18px;
  margin-left: 18px;
}

.ty-preferences .pane-sm .search-input {
  margin: 0rem !important;
  width: 100%;
  font-size: 1rem !important;
  height: 2.75rem;
}

.ty-preferences .pane-sm .search-input:active,
.ty-preferences .pane-sm .search-input:focus {
  border: solid 1px var(--primary-color) !important;
  outline: none;
}

/*preferences main*/
.ty-preferences .panel-header {
  font-weight: 600;
  font-size: 1.6rem;
}

/*preferences stuff*/
.ty-preferences .dropdown-menu > li,
.dropdown-item {
  font-weight: 500;
  font-size: 1rem;
  transition-duration: 0.2s;
  transition-property: all;
}

.ty-preferences .dropdown-menu .active,
.ty-preferences .dropdown-menu li:hover,
.dropdown-item:hover {
  background-color: var(--boxes);
  color: var(--primary-color);
}

#ty-spell-check-dict-missing-secondary-btn:hover {
  color: var(--primary-color) !important;
}

.header-close .icon {
  border: none !important;
}

/*DROPDOWN*/

.dropdown-menu:not(.megamenu-menu-list),
.auto-suggest-container {
  background-color: var(--bg-color);
  border: solid 1px var(--borders) !important;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
  user-select: none;
}

.dropdown-menu > li > a {
  font-weight: 500;
  font-size: 0.8rem;
  transition-duration: 0.2s;
  transition-property: all;
}

.dropdown-menu > .active > a,
.dropdown-menu > li > a:hover,
.menu-style-btn.active,
.context-menu.dropdown-menu > .active > a,
.context-menu.dropdown-menu > li > a:hover {
  color: var(--primary-color);
  background-color: var(--boxes);
}

.menu-style-btn {
  color: var(--text-color);
  border: none;
  transition-duration: 0.2s;
  transition-property: all;
}

.menu-style-btn:hover {
  color: var(--primary-color);
  background-color: var(--boxes);
  border: none;
}

header .menu-style-btn:hover {
  background-color: transparent;
}

.menu-item-container {
  padding: 0 12px 0 4px;
}

.menu-item-container a.menu-style-btn {
  padding: 0.3rem 0.6rem;
  margin: 0;
}

.dropdown-menu .divider {
  border-color: var(--borders);
}

/*BUTTON*/

.btn,
button {
  border: none !important;
  border-radius: 0.3em !important;
  color: var(--text-color) !important;
  transition-duration: 0.2s;
  transition-property: all;
  font-size: 0.9em !important;
  font-weight: 500;
  outline: none;
}

.btn-default {
  border: none !important;
  border-radius: 0.3em !important;
  background-color: var(--boxes) !important;
}

.btn:hover,
.button-hover {
  border: none;
  border-radius: 0.3em;
  background-color: var(--borders) !important;
  color: var(--text-color);
}

button:active,
button.active,
.btn:active,
.btn-default:active {
  border: none;
  border-radius: 0.3em;
  background-color: var(--boxes-darker) !important;
  box-shadow: none;
  outline: none;
  color: var(--text-color);
}

.btn:focus {
  border: none !important;
  outline: none !important;
  background-color: var(--boxes-darker);
}

.btn-primary {
  border: none;
  border-radius: 0.3em;
  background-color: var(--primary-color);
  color: white !important;
}

.btn-primary:hover,
.btn-primary:focus {
  color: white;
  background-color: var(--primary-color-darker) !important;
}

.btn.dropdown-toggle-split,
.btn.dropdown-toggle-split:hover {
  border-radius: 0em 0.3em 0.3em 0em !important;
}

#ty-spell-check-dict-missing-primary-btn {
  border-radius: 0.3em 0em 0em 0.3em !important;
}

.open > .dropdown-toggle.btn-primary {
  background-color: var(--primary-color);
  border-color: transparent;
}

/*GHOST BUTTON*/

.window-header button,
#close-sidebar-menu-btn,
.html-for-mac .sidebar-tab-btn,
.label-hint,
.ty-table-edit .btn,
.zoom-hint-button {
  background-color: transparent !important;
  color: var(--light-text-color) !important;
  opacity: 1 !important;
  transition-duration: 0.2s;
  transition-property: color;
}

.window-header button:hover,
.window-header button:focus,
#close-sidebar-menu-btn:hover,
#close-sidebar-menu-btn:focus,
.html-for-mac .sidebar-tab-btn:hover,
.html-for-mac .sidebar-tab-btn:focus,
.label-hint:hover,
.label-hint:focus,
.ty-table-edit .btn:hover,
.ty-table-edit .btn:focus,
.zoom-hint-button:hover,
.zoom-hint-button:focus {
  color: var(--primary-color) !important;
  background: none !important;
}

.ty-table-edit .btn.active {
  color: var(--primary-color) !important;
  box-shadow: none;
}

/*IMAGE BUTTON*/

.md-image-btn {
  background-color: var(--boxes);
  transition-duration: 0.2s;
  transition-property: background-color;
}

.md-image-btn:before {
  color: var(--text-color);
  transition-duration: 0.2s;
  transition-property: color;
}

.md-image-btn:hover {
  background-color: var(--borders);
}

.md-image-btn:hover:before {
  color: var(--primary-color);
}

.md-image-input-src-btn {
  border-radius: 0.3rem 0rem 0rem 0.3rem !important;
}

.md-image-pick-file-btn {
  border-left: none;
  border-radius: 0rem 0.3rem 0.3rem 0rem !important;
}

/*SEARCH-INPUTS*/

.search-input,
.search,
.form-control,
#file-library-search-input {
  background-color: transparent !important;
  border-radius: 0.3rem !important;
  border: solid 1px var(--boxes-darker2) !important;
  box-shadow: none !important;
  color: var(---heading-text-color) !important;
  font-size: 0.9rem !important;
  font-weight: 500;
  padding: 0.7rem !important;
  height: 2rem;
  transition-duration: 0.2s;
  transition-property: border;
}

.search-input:focus,
.search:focus,
.form-control:focus,
#file-library-search-input:focus {
  background-color: transparent !important;
  border-radius: 0r3em !important;
  border-color: var(--primary-color) !important;
  box-shadow: none !important;
  color: var(--heading-text-color) !important;
  font-size: 0.9rem !important;
  font-weight: 500;
  padding: 0.7rem !important;
}

.search-input::placeholder,
.search::placeholder,
.form-control::placeholder,
#file-library-search-input::placeholder {
  color: var(--light-text-color-darker) !important;
}

.clear-btn-icon {
  top: 9px !important /*required*/;
  right: 9px !important /*required*/;
}

.content tr.search-hit,
.search-hit,
.md-search-hit,
.md-search-hit.md-search-select,
.md-search-select,
.ty-file-search-match-text {
  background: rgba(56, 132, 255, 0.3) !important;
}

/*ZOOM HINT*/

#zoom-hint {
  border-radius: 0.3rem;
  border: solid 1px var(--borders);
  user-select: none;
  box-shadow: rgba(116, 129, 141, 0.08) 0px 2px 6px 0px;
}

#zoom-hint #zoom-hint-reset {
  border-left: none;
  font-weight: 600;
}

/*SEARCHPANEL*/

#md-searchpanel {
  border-bottom: 1px solid var(--borders);
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
  max-height: 46px;
}

#md-searchpanel.searchpanel-replace-mode {
  max-height: 84px;
}

#md-searchpanel input {
  height: 2rem;
  margin: 0rem !important;
  padding: 6px 12px !important;
  font-size: 12px !important;
}

#md-searchpanel .input-group-addon {
  height: 2rem;
}

#md-searchpanel .input-group-addon.close-btn {
  padding-left: 8px;
}

.unibody-window #md-searchpanel .btn {
  line-height: 2rem;
}

.searchpanel-search-option-btn {
  top: 9px;
  border: none;
  color: var(--light-text-color-darker) !important /*required*/;
  transition-duration: 0.3s;
}

.searchpanel-search-option-btn:hover {
  color: var(--primary-color) !important /*required*/;
  background-color: transparent !important /*required*/;
}

.searchpanel-search-option-btn.select,
.searchpanel-search-option-btn.active {
  color: white !important;
  background-color: var(--primary-color) !important;
}

#searchpanel-case-option-btn {
  right: 33px;
}

#searchpanel-word-option-btn {
  right: 9px;
}

#searchpanel-word-option-btn,
#searchpanel-case-option-btn {
  background: none;
}

#md-searchpanel .btn:not(.close-btn):hover {
  box-shadow: none;
}

/*NUMBER-INPUT*/
input[type='number'] {
  background-color: var(--boxes) !important;
  border: none !important;
  border-radius: 0.3rem;
}

input[type='number']:focus {
  background-color: var(--item-hover-bg-color) !important;
}

/*SELECTS*/

select {
  background-color: var(--bg-color) !important;
  border-radius: 0.3rem !important;
  border: solid 1px var(--boxes-darker2) !important;
  box-shadow: none !important;
  color: var(---heading-text-color) !important;
  font-size: 0.9rem !important;
  font-weight: 500 !important;
  padding: 0.3rem !important;
  height: 2.1rem;
  transition-duration: 0.2s;
  transition-property: border;
}

select:hover {
  background-color: var(--bg-color) !important;
  border-radius: 0r3em !important;
  border-color: var(--primary-color) !important;
  box-shadow: none !important;
  color: var(--heading-text-color) !important;
  font-size: 0.9rem !important;
}

/*MODAL*/

.modal-header,
#common-dialog .modal-header {
  border-bottom: solid 1px var(--borders);
  padding-bottom: 15px;
}

.modal-title {
  font-size: 1.25rem;
  font-weight: 500;
  user-select: none;
}

.modal-body {
  font-size: 0.9rem;
  color: var(--light-text-color-darker);
  user-select: none;
}

.modal-content {
  box-shadow: rgba(116, 129, 141, 0.15) 0px 3px 10px 0px;
  border: solid 1px var(--boxes-darker);
  border-radius: 0.3rem;
}

.modal-footer {
  border-top: solid 1px var(--borders);
}

.modal-open .modal.fade.in {
  background: none;
  backdrop-filter: blur(5px);
}

/*SCROLLBAR*/

::-webkit-scrollbar {
  width: 9px;
  height: 8px;
  position: absolute;
  border-radius: 4.5px;
}

::-webkit-scrollbar:hover {
  background-color: transparent;
}

::-webkit-scrollbar-corner {
  background: 0 0;
}

::-webkit-scrollbar-thumb {
  background: var(--boxes-darker2);
  background-clip: padding-box;
  border-radius: 4.5px;
}

::-webkit-scrollbar-thumb:hover {
  background: var(--boxes-darkest);
}

::-webkit-scrollbar-thumb:active {
  background: var(--boxes-darkest);
}

/*LANGS*/

.ty-spell-check-panel-item {
  font-weight: 500;
  transition-duration: 0.2s;
  transition-property: background-color, color;
}

.ty-spell-check-panel-item:hover {
  color: var(--primary-color);
  background-color: var(--boxes);
}

.ty-spell-check-panel-item.ty-active {
  background-color: var(--boxes);
}

/*TOOLTIP*/

.ty-tooltip {
  background-color: var(--bg-color) !important;
  border-radius: 0.3rem !important;
  border: 1px solid var(--borders) !important;
  -webkit-filter: none !important;
  filter: none;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 3px 8px 0px;
}

/*FOOTER*/

.footer-item:hover {
  background-color: var(--boxes) !important;
}

#footer-word-count-info {
  padding: 4px 0;
}

.footer-word-count-info-line {
  padding: 0.25rem;
  line-height: 1.6rem;
}

#footer-word-count-info tr {
  font-weight: 500;
  font-size: 0.8rem;
  transition-duration: 0.2s;
  transition-property: all;
}

#footer-word-count-info tr td:nth-child(1) {
  padding: 0rem;
  padding-right: 1rem;
}

#footer-word-count-info .ty-footer-word-count-all tr:hover {
  color: var(--primary-color) !important;
  background-color: var(--boxes) !important;
}

/*MEGAMENU*/

.megamenu-menu {
  box-shadow: none;
  background-color: var(--boxes);
  border-right: 1px solid var(--borders);
}

.megamenu-opened .megamenu-menu {
  left: 0px;
}

#megamenu-content {
  top: 0px;
  left: 0px;
  right: 0px;
  bottom: 0px;
}

#megamenu-menu-list {
  box-shadow: none;
  border: none;
  background-color: transparent;
}

#megamenu-menu-list li a {
  color: var(--text-color);
  height: 2rem;
  line-height: 1.8rem;
  transition-duration: 0.2s;
  transition-property: background-color;
}

#megamenu-menu-list li a:hover {
  background-color: var(--borders);
}

#megamenu-menu-list li a.active {
  color: var(--primary-color);
  background-color: white;
  outline: solid 1px var(--borders);
}

#megamenu-menu-list .divider {
  background-color: var(--borders);
  margin: 16px 0 0 0;
}

.megamenu-menu-list .saved #m-saved {
  cursor: default;
}

.megamenu-menu-list .saved #m-saved .fa {
  color: var(--primary-color);
}

.megamenu-menu-list .saved #m-saved:hover {
  background-color: transparent;
}

.megamenu-menu-list #m-close:hover {
  color: var(--danger-color);
}

.megamenu-menu-header {
  border-bottom: solid 1px var(--borders);
  margin-bottom: 1.2rem;
  height: 74px;
  transition-duration: 0.3s;
}

.megamenu-menu-header:hover {
  background-color: var(--borders);
}

.megamenu-menu-header #megamenu-menu-header-title {
  color: var(--text-color);
  font-weight: 700;
  font-size: 16px;
  left: 56px;
  top: 24px;
}

#megamenu-back-btn {
  color: var(--text-color);
  font-size: 16px;
  left: 24px;
  top: 24px;
}

.megamenu-opened header {
  background-color: var(--bg-color);
  background-image: none;
}

.megamenu-content {
  background-color: var(--bg-color);
  background-image: none;
}

.megamenu-menu-panel:not(:first-of-type) {
  margin-top: 2rem;
}

.megamenu-menu-panel h1 {
  font-weight: 900;
  font-size: 1.8rem;
  margin: 1rem 0rem 0.4rem 0rem;
}

.megamenu-menu-panel h2 {
  font-weight: 800;
  font-size: 1.3rem;
  margin: 1rem 0rem 0.4rem 0rem;
}

/*recent files*/

#recent-file-panel tbody tr {
  font-weight: 600;
  transition-duration: 0.4s;
}

#recent-file-panel tbody tr:hover,
.megamenu-menu-panel tbody tr:hover td:nth-child(1) {
  color: var(--primary-color);
}

#recent-file-panel tbody tr:nth-child(2n-1) {
  background-color: var(--boxes);
}

/*about help*/

.about-content-slogon {
  color: var(--light-text-color);
}

/*for the god himself*/
.about-content-slogon span {
  color: var(--primary-color) !important;
}

#about-content tbody tr {
  font-weight: 500;
  transition-duration: 0.4s;
}

#about-content tbody tr:hover {
  color: var(--primary-color);
  background-color: var(--boxes) !important /*required important*/;
}

.long-btn {
  margin-bottom: 12px;
  margin-left: 2px;
  box-shadow: rgba(116, 129, 141, 0.1) 2px 2px 6px;
  background-color: white;
  border: 1px solid var(--borders);
  border-radius: 0.3rem;
  padding: 1rem;

  font-weight: 700;
  font-size: 1rem;

  transition: background 0.2s, color 0.2s, box-shadow 0.2s;
}

.long-btn:hover {
  background-color: var(--primary-color);
  border: 1px solid transparent;
  color: white !important /*important required*/;
  box-shadow: rgba(116, 129, 141, 0.1) 2px 2px 6px, rgba(56, 132, 255, 0.2) 0px 0px 10px;
}

#m-import-local:hover .preference-item-hint {
  color: white;
  opacity: 0.7;
}

#recent-file-panel-action-btn {
  height: 34px;
  border: none;
  background-color: var(--boxes);
}

#theme-preview-grid {
  max-width: none;
  padding: 1.5rem;
  background-color: var(--boxes);
  border-radius: 0rem;
  display: grid;
  grid-template-columns: repeat(auto-fill, minmax(300px, 1fr));
  grid-gap: 1.5rem;
}

.theme-preview-div {
  border: none;
  border-radius: 0.4rem;
  box-shadow: rgba(116, 129, 141, 0.1) 0px 0px 15px;
  margin: 0rem;
  transition-duration: 0.3s;
}

.theme-preview-div:hover {
  box-shadow: rgba(116, 129, 141, 0.5) 3px 8px 15px;
  cursor: pointer;
  transform: rotate3d(1, -0.2, 0.2, 15deg);
}

.theme-preview-content {
  width: 100%;
  height: 100%;
  border-radius: 0.4rem;
}

.theme-preview-content html {
  width: 100%;
  height: 100%;
}

.theme-preview-div.active .fa {
  color: var(--primary-color);
  bottom: 4px;
  left: 4px;
}

.theme-preview-div .fa-check-circle:before {
  background-color: var(--bg-color);
  padding: 0px 2px;
  border-radius: 1rem;
}

.megamenu-menu-panel tbody tr {
  border-radius: 0.3rem;
  transition-duration: 0.2s;
  transition-property: background-color;
}

.megamenu-menu-panel tbody tr:hover {
  background-color: var(--borders) !important /*required important*/;
}

/*MIN MAX CLOSE*/
#w-min,
#w-max,
#w-restore,
#w-close {
  border-radius: 0px !important;
  font-size: 10px !important;
  width: 46px !important;
  height: 29px !important;
}

.btn.toolbar-icon svg,
.btn.toolbar-icon .ty-icon {
  position: relative;
  top: 2px;
}

#w-close.btn.toolbar-icon .ty-icon {
  left: 1px;
}

#w-close:hover {
  background-color: var(--danger-color) !important;
  color: white !important;
}

/*EXTRA STUFF*/

a[type='page-link'] {
  display: block;
  background-color: white;
  box-shadow: rgba(116, 129, 141, 0.2) 0px 3px 8px 0px;
  border: 1px solid var(--borders);
  border-radius: 0.3rem;
  padding: 1rem;

  font-weight: 600;

  transition-duration: 0.2s;
  transition-property: border, box-shadow;
}

a[type='page-link']:hover {
  box-shadow: rgba(116, 129, 161, 0.1) 0px 3px 8px 0px;
  border: 1px solid var(--primary-color);
}

p[type='description'] {
  color: var(--light-text-color);
  margin: 0rem;
  margin-bottom: 1rem;
}


 :root {--mermaid-font-zoom:1.25em ;} 
</style>
</head>
<body class='typora-export os-windows'>
<div id='write'  class=''><h2><a name="常用模型" class="md-header-anchor"></a><span>常用模型</span></h2><ul><li><span>01背包</span></li><li><span>完全背包</span></li><li><span>多重背包</span></li><li><span>分组背包</span></li><li><span>二维费用背包</span></li><li><span>有依赖的背包</span></li></ul><h2><a name="0-1背包" class="md-header-anchor"></a><span>0-1背包</span></h2><p><span>每件物品最多只用一次</span></p><blockquote><p><span>详细描述：有N件物品和一个容量是V的背包，每件物品只能使用一次。</span></p><p><span>第 i 件物品的体积是 vi，价值是wi</span></p><p><span>求解将哪些物品装进背包，可使这些物品的总体积不超过背包容量，且总价值最大</span></p></blockquote><p><img src="https://pic.downk.cc/item/5f1d1a3b14195aa59482907d.png" referrerpolicy="no-referrer"></p><p><img src="https://pic.downk.cc/item/5f1d1a3b14195aa59482907f.png" referrerpolicy="no-referrer"></p><p><span>对上图进行一下补充：在计算含i的状态时，我们将其分为变化的部分和不变的部分</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.00006px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation"><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">变化的部分</span> &nbsp;<span class="cm-variable">必选部分</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-number">1.</span> <span class="cm-operator">----------</span> <span class="cm-variable">i</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-number">2.</span> <span class="cm-operator">----------</span> <span class="cm-variable">i</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">那么变化的部分的最大值，就是</span> <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]], <span class="cm-variable">在加上w</span>[<span class="cm-variable">i</span>]<span class="cm-variable">即为我们所求</span></span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 115px;"></div><div class="CodeMirror-gutters" style="height: 115px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>代码：朴素版本   </span><span class="MathJax_SVG" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="6.754ex" height="2.838ex" viewBox="0 -915.3 2908.1 1221.7" role="img" focusable="false" style="vertical-align: -0.712ex;"><defs><path stroke-width="0" id="E6-MJMATHI-4F" d="M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z"></path><path stroke-width="0" id="E6-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E6-MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path><path stroke-width="0" id="E6-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="0" id="E6-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E6-MJMATHI-4F" x="0" y="0"></use><use xlink:href="#E6-MJMAIN-28" x="763" y="0"></use><g transform="translate(1152,0)"><use xlink:href="#E6-MJMATHI-4E" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E6-MJMAIN-32" x="1291" y="513"></use></g><use xlink:href="#E6-MJMAIN-29" x="2519" y="0"></use></g></svg></span><script type="math/tex"> O(N^2) </script></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><span><span>​</span>x</span></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;bits/stdc++.h&gt;</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">using</span> <span class="cm-keyword">namespace</span> <span class="cm-def">std</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">const</span> <span class="cm-variable-3">int</span> <span class="cm-variable">N</span> <span class="cm-operator">=</span> <span class="cm-number">1010</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-variable">n</span>, <span class="cm-variable">m</span>; <span class="cm-comment">// n 表示物品数量， m表示背包容积</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">7</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-variable">v</span>[<span class="cm-variable">N</span>], <span class="cm-variable">w</span>[<span class="cm-variable">N</span>]; <span class="cm-comment">// vi表示体积，wi表示价值</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">8</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-variable">f</span>[<span class="cm-variable">N</span>][<span class="cm-variable">N</span>]; <span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-comment">// fij 表示所有方案中，从前i个物品中选并体积不超过j的最大价值</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">9</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">10</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-def">main</span>() {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">11</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">n</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">m</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">12</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) <span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">13</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) { <span class="cm-comment">// 从1个不选到n个全要</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">14</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>) { <span class="cm-comment">// 体积从1-m</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">15</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span>]; <span class="cm-comment">// 不包含i的情况</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">16</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span> (<span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">17</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">18</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">19</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">20</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">21</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">cout</span> <span class="cm-operator">&lt;&lt;</span> <span class="cm-variable">f</span>[<span class="cm-variable">n</span>][<span class="cm-variable">m</span>] <span class="cm-operator">&lt;&lt;</span> <span class="cm-variable">endl</span>; <span class="cm-comment">// fnm 表示从前n个中选择，体积为m的最大价值</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">22</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">return</span> <span class="cm-number">0</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">23</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 662px;"></div><div class="CodeMirror-gutters" style="height: 662px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>重点是状态转移方程：</span></p><div contenteditable="false" spellcheck="false" class="mathjax-block md-end-block md-math-block md-rawblock" id="mathjax-n29" cid="n29" mdtype="math_block"><div class="md-rawblock-container md-math-container" tabindex="-1"><div class="MathJax_SVG_Display" style="text-align: center;"><span class="MathJax_SVG" id="MathJax-Element-1-Frame" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="48.043ex" height="2.636ex" viewBox="0 -828.3 20685 1134.7" role="img" focusable="false" style="vertical-align: -0.712ex; max-width: 100%;"><defs><path stroke-width="0" id="E1-MJMATHI-66" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path stroke-width="0" id="E1-MJMAIN-5B" d="M118 -250V750H255V710H158V-210H255V-250H118Z"></path><path stroke-width="0" id="E1-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E1-MJMAIN-5D" d="M22 710V750H159V-250H22V-210H119V710H22Z"></path><path stroke-width="0" id="E1-MJMATHI-6A" d="M297 596Q297 627 318 644T361 661Q378 661 389 651T403 623Q403 595 384 576T340 557Q322 557 310 567T297 596ZM288 376Q288 405 262 405Q240 405 220 393T185 362T161 325T144 293L137 279Q135 278 121 278H107Q101 284 101 286T105 299Q126 348 164 391T252 441Q253 441 260 441T272 442Q296 441 316 432Q341 418 354 401T367 348V332L318 133Q267 -67 264 -75Q246 -125 194 -164T75 -204Q25 -204 7 -183T-12 -137Q-12 -110 7 -91T53 -71Q70 -71 82 -81T95 -112Q95 -148 63 -167Q69 -168 77 -168Q111 -168 139 -140T182 -74L193 -32Q204 11 219 72T251 197T278 308T289 365Q289 372 288 376Z"></path><path stroke-width="0" id="E1-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="0" id="E1-MJMATHI-6D" d="M21 287Q22 293 24 303T36 341T56 388T88 425T132 442T175 435T205 417T221 395T229 376L231 369Q231 367 232 367L243 378Q303 442 384 442Q401 442 415 440T441 433T460 423T475 411T485 398T493 385T497 373T500 364T502 357L510 367Q573 442 659 442Q713 442 746 415T780 336Q780 285 742 178T704 50Q705 36 709 31T724 26Q752 26 776 56T815 138Q818 149 821 151T837 153Q857 153 857 145Q857 144 853 130Q845 101 831 73T785 17T716 -10Q669 -10 648 17T627 73Q627 92 663 193T700 345Q700 404 656 404H651Q565 404 506 303L499 291L466 157Q433 26 428 16Q415 -11 385 -11Q372 -11 364 -4T353 8T350 18Q350 29 384 161L420 307Q423 322 423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 181Q151 335 151 342Q154 357 154 369Q154 405 129 405Q107 405 92 377T69 316T57 280Q55 278 41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E1-MJMATHI-61" d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z"></path><path stroke-width="0" id="E1-MJMATHI-78" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path stroke-width="0" id="E1-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E1-MJMAIN-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path stroke-width="0" id="E1-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="0" id="E1-MJMAIN-2C" d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z"></path><path stroke-width="0" id="E1-MJMATHI-76" d="M173 380Q173 405 154 405Q130 405 104 376T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Q21 294 29 316T53 368T97 419T160 441Q202 441 225 417T249 361Q249 344 246 335Q246 329 231 291T200 202T182 113Q182 86 187 69Q200 26 250 26Q287 26 319 60T369 139T398 222T409 277Q409 300 401 317T383 343T365 361T357 383Q357 405 376 424T417 443Q436 443 451 425T467 367Q467 340 455 284T418 159T347 40T241 -11Q177 -11 139 22Q102 54 102 117Q102 148 110 181T151 298Q173 362 173 380Z"></path><path stroke-width="0" id="E1-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="0" id="E1-MJMATHI-77" d="M580 385Q580 406 599 424T641 443Q659 443 674 425T690 368Q690 339 671 253Q656 197 644 161T609 80T554 12T482 -11Q438 -11 404 5T355 48Q354 47 352 44Q311 -11 252 -11Q226 -11 202 -5T155 14T118 53T104 116Q104 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Q21 293 29 315T52 366T96 418T161 441Q204 441 227 416T250 358Q250 340 217 250T184 111Q184 65 205 46T258 26Q301 26 334 87L339 96V119Q339 122 339 128T340 136T341 143T342 152T345 165T348 182T354 206T362 238T373 281Q402 395 406 404Q419 431 449 431Q468 431 475 421T483 402Q483 389 454 274T422 142Q420 131 420 107V100Q420 85 423 71T442 42T487 26Q558 26 600 148Q609 171 620 213T632 273Q632 306 619 325T593 357T580 385Z"></path><path stroke-width="0" id="E1-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E1-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="550" y="0"></use><use xlink:href="#E1-MJMATHI-69" x="828" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="1173" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="1451" y="0"></use><use xlink:href="#E1-MJMATHI-6A" x="1729" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="2141" y="0"></use><use xlink:href="#E1-MJMAIN-3D" x="2696" y="0"></use><use xlink:href="#E1-MJMATHI-6D" x="3752" y="0"></use><use xlink:href="#E1-MJMATHI-61" x="4630" y="0"></use><use xlink:href="#E1-MJMATHI-78" x="5159" y="0"></use><use xlink:href="#E1-MJMAIN-28" x="5731" y="0"></use><use xlink:href="#E1-MJMATHI-66" x="6120" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="6670" y="0"></use><use xlink:href="#E1-MJMATHI-69" x="6948" y="0"></use><use xlink:href="#E1-MJMAIN-2212" x="7515" y="0"></use><use xlink:href="#E1-MJMAIN-31" x="8516" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="9016" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="9294" y="0"></use><use xlink:href="#E1-MJMATHI-6A" x="9572" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="9984" y="0"></use><use xlink:href="#E1-MJMAIN-2C" x="10262" y="0"></use><use xlink:href="#E1-MJMATHI-66" x="10706" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="11256" y="0"></use><use xlink:href="#E1-MJMATHI-69" x="11534" y="0"></use><use xlink:href="#E1-MJMAIN-2212" x="12101" y="0"></use><use xlink:href="#E1-MJMAIN-31" x="13102" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="13602" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="13880" y="0"></use><use xlink:href="#E1-MJMATHI-6A" x="14158" y="0"></use><use xlink:href="#E1-MJMAIN-2212" x="14792" y="0"></use><use xlink:href="#E1-MJMATHI-76" x="15792" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="16277" y="0"></use><use xlink:href="#E1-MJMATHI-69" x="16555" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="16900" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="17178" y="0"></use><use xlink:href="#E1-MJMAIN-2B" x="17678" y="0"></use><use xlink:href="#E1-MJMATHI-77" x="18679" y="0"></use><use xlink:href="#E1-MJMAIN-5B" x="19395" y="0"></use><use xlink:href="#E1-MJMATHI-69" x="19673" y="0"></use><use xlink:href="#E1-MJMAIN-5D" x="20018" y="0"></use><use xlink:href="#E1-MJMAIN-29" x="20296" y="0"></use></g></svg></span></div><script type="math/tex; mode=display" id="MathJax-Element-1">\begin{equation}
	f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])
\end{equation}</script></div></div><p><strong><span>代码优化思路：</span></strong><span> i 只用到了</span><code>f[i]</code><span>和 </span><code>f[i-1]</code><span>这两层，j 只用到了 </span><code>j</code><span> 和 </span><code>j - vi</code></p><p><span>我们一步一步来看（对代码进行恒等变形）：</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>14</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) { <span class="cm-comment">// 从1个不选到n个全要</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>) { <span class="cm-comment">// 体积从1-m</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span>];<span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-comment">// 不包含i的情况</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// 1. f[i][j] = f[i-1][j]; </span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-comment">// 计算顺序时先计算右边，然后再更新左边，此时右面的值还在上一层</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span> (<span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">7</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; <span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">8</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// 由于我们时从小到大的枚举j，且 j - v[i] &lt; j</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">9</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// 所以 f[j-v[i]] 一定是再 f[j] 之前被算出来的，于是等价于</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">10</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]) 不符合</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">11</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// 只需要从大到小枚举j就可以解决</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">12</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">13</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">14</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 403px;"></div><div class="CodeMirror-gutters" style="height: 403px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>修改过后的代码：</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>3</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation"><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]; <span class="cm-variable">j</span> <span class="cm-operator">--</span>) </span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 86px;"></div><div class="CodeMirror-gutters" style="height: 86px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>注：将j循环改成由大到小之后，就可以保证，先计算</span><code>f[j]</code><span>而后计算的</span><code>f[j-v[i]]</code><span>，等价于</span><code>f[i-1][j-v[i]]</code></p><p><span>我们只有上一层dp值的一维数组，更新dp值只能原地滚动更改；</span></p><p><span>注意到，当我们更新索引值较大的dp值时</span><code>dp[j]</code><span>，需要用到上一层dp值</span><code>dp[j - v[i]]</code><span>，也就是说，在更新索引值较大的dp值之前，索引值较小的</span><code>上一层dp值必须还在</code><span>，还没被更新；</span></p><p><span>所以只能索引从大到小更新，否则会发生覆盖现象。</span></p><blockquote><p><strong><span>如果没看明白，继续看完 完全背包后的总结</span></strong></p></blockquote><p><span>PS：一些其他小问题</span></p><blockquote><p><span>Q：yls为什么背包九讲里说：最终的答案并不一定是</span><code>f[N][V]</code><span>，而是</span><code>f[N][0-V]</code><span>的最大值呢？</span></p><p><span>A：取决于状态的定义是“</span><code>恰好使用</code><span>V的体积，还是</span><code>最多使用</code><span>V的体积”。</span></p></blockquote><!--more--><h2><a name="完全背包" class="md-header-anchor"></a><span>完全背包</span></h2><p><span>每件物品有无限个</span></p><p><img src="https://pic.imgdb.cn/item/5f1d351414195aa594961788.jpg" referrerpolicy="no-referrer"></p><p><span>根据这个状态转移方程，我们可以写出一个三层循环的朴素版本</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>4</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation"><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">k</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">k</span> <span class="cm-operator">*</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&lt;=</span> <span class="cm-variable">j</span>; <span class="cm-variable">k</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">k</span> <span class="cm-operator">*</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">k</span> <span class="cm-operator">*</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 115px;"></div><div class="CodeMirror-gutters" style="height: 115px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>优化的时候我们可以着重优化第三重循环</span></p><div contenteditable="false" spellcheck="false" class="mathjax-block md-end-block md-math-block md-rawblock" id="mathjax-n52" cid="n52" mdtype="math_block"><div class="md-rawblock-container md-math-container" tabindex="-1"><div class="MathJax_SVG_Display" style="text-align: center;"><span class="MathJax_SVG" id="MathJax-Element-2-Frame" tabindex="-1" style="font-size: 100%; display: inline-block; zoom: 0.942729;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="86.789ex" height="5.868ex" viewBox="0 -1524.2 37367.5 2526.4" role="img" focusable="false" style="vertical-align: -2.328ex; max-width: 100%;"><defs><path stroke-width="0" id="E8-MJMATHI-66" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path stroke-width="0" id="E8-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E8-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E8-MJMAIN-2C" d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z"></path><path stroke-width="0" id="E8-MJMATHI-6A" d="M297 596Q297 627 318 644T361 661Q378 661 389 651T403 623Q403 595 384 576T340 557Q322 557 310 567T297 596ZM288 376Q288 405 262 405Q240 405 220 393T185 362T161 325T144 293L137 279Q135 278 121 278H107Q101 284 101 286T105 299Q126 348 164 391T252 441Q253 441 260 441T272 442Q296 441 316 432Q341 418 354 401T367 348V332L318 133Q267 -67 264 -75Q246 -125 194 -164T75 -204Q25 -204 7 -183T-12 -137Q-12 -110 7 -91T53 -71Q70 -71 82 -81T95 -112Q95 -148 63 -167Q69 -168 77 -168Q111 -168 139 -140T182 -74L193 -32Q204 11 219 72T251 197T278 308T289 365Q289 372 288 376Z"></path><path stroke-width="0" id="E8-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path stroke-width="0" id="E8-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="0" id="E8-MJMATHI-4D" d="M289 629Q289 635 232 637Q208 637 201 638T194 648Q194 649 196 659Q197 662 198 666T199 671T201 676T203 679T207 681T212 683T220 683T232 684Q238 684 262 684T307 683Q386 683 398 683T414 678Q415 674 451 396L487 117L510 154Q534 190 574 254T662 394Q837 673 839 675Q840 676 842 678T846 681L852 683H948Q965 683 988 683T1017 684Q1051 684 1051 673Q1051 668 1048 656T1045 643Q1041 637 1008 637Q968 636 957 634T939 623Q936 618 867 340T797 59Q797 55 798 54T805 50T822 48T855 46H886Q892 37 892 35Q892 19 885 5Q880 0 869 0Q864 0 828 1T736 2Q675 2 644 2T609 1Q592 1 592 11Q592 13 594 25Q598 41 602 43T625 46Q652 46 685 49Q699 52 704 61Q706 65 742 207T813 490T848 631L654 322Q458 10 453 5Q451 4 449 3Q444 0 433 0Q418 0 415 7Q413 11 374 317L335 624L267 354Q200 88 200 79Q206 46 272 46H282Q288 41 289 37T286 19Q282 3 278 1Q274 0 267 0Q265 0 255 0T221 1T157 2Q127 2 95 1T58 0Q43 0 39 2T35 11Q35 13 38 25T43 40Q45 46 65 46Q135 46 154 86Q158 92 223 354T289 629Z"></path><path stroke-width="0" id="E8-MJMATHI-61" d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z"></path><path stroke-width="0" id="E8-MJMATHI-78" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path stroke-width="0" id="E8-MJMAIN-5B" d="M118 -250V750H255V710H158V-210H255V-250H118Z"></path><path stroke-width="0" id="E8-MJMAIN-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path stroke-width="0" id="E8-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="0" id="E8-MJMAIN-5D" d="M22 710V750H159V-250H22V-210H119V710H22Z"></path><path stroke-width="0" id="E8-MJMATHI-76" d="M173 380Q173 405 154 405Q130 405 104 376T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Q21 294 29 316T53 368T97 419T160 441Q202 441 225 417T249 361Q249 344 246 335Q246 329 231 291T200 202T182 113Q182 86 187 69Q200 26 250 26Q287 26 319 60T369 139T398 222T409 277Q409 300 401 317T383 343T365 361T357 383Q357 405 376 424T417 443Q436 443 451 425T467 367Q467 340 455 284T418 159T347 40T241 -11Q177 -11 139 22Q102 54 102 117Q102 148 110 181T151 298Q173 362 173 380Z"></path><path stroke-width="0" id="E8-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="0" id="E8-MJMATHI-77" d="M580 385Q580 406 599 424T641 443Q659 443 674 425T690 368Q690 339 671 253Q656 197 644 161T609 80T554 12T482 -11Q438 -11 404 5T355 48Q354 47 352 44Q311 -11 252 -11Q226 -11 202 -5T155 14T118 53T104 116Q104 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Q21 293 29 315T52 366T96 418T161 441Q204 441 227 416T250 358Q250 340 217 250T184 111Q184 65 205 46T258 26Q301 26 334 87L339 96V119Q339 122 339 128T340 136T341 143T342 152T345 165T348 182T354 206T362 238T373 281Q402 395 406 404Q419 431 449 431Q468 431 475 421T483 402Q483 389 454 274T422 142Q420 131 420 107V100Q420 85 423 71T442 42T487 26Q558 26 600 148Q609 171 620 213T632 273Q632 306 619 325T593 357T580 385Z"></path><path stroke-width="0" id="E8-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="0" id="E8-MJMAIN-2E" d="M78 60Q78 84 95 102T138 120Q162 120 180 104T199 61Q199 36 182 18T139 0T96 17T78 60Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(167,0)"><g transform="translate(-18,0)"><g transform="translate(1707,650)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-28" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="939" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="1284" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="1728" y="0"></use><use xlink:href="#E8-MJMAIN-29" x="2140" y="0"></use></g><g transform="translate(0,-700)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-28" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="939" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="1284" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="1728" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="2362" y="0"></use><use xlink:href="#E8-MJMATHI-76" x="3363" y="0"></use><use xlink:href="#E8-MJMAIN-29" x="3848" y="0"></use></g></g><g transform="translate(4219,0)"><g transform="translate(0,650)"><use xlink:href="#E8-MJMAIN-3D" x="277" y="0"></use><use xlink:href="#E8-MJMATHI-4D" x="1333" y="0"></use><use xlink:href="#E8-MJMATHI-61" x="2384" y="0"></use><use xlink:href="#E8-MJMATHI-78" x="2913" y="0"></use><use xlink:href="#E8-MJMAIN-28" x="3485" y="0"></use><use xlink:href="#E8-MJMATHI-66" x="3874" y="0"></use><use xlink:href="#E8-MJMAIN-5B" x="4424" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="4702" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="5269" y="0"></use><use xlink:href="#E8-MJMAIN-31" x="6270" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="6770" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="7214" y="0"></use><use xlink:href="#E8-MJMAIN-5D" x="7626" y="0"></use></g><g transform="translate(0,-700)"><use xlink:href="#E8-MJMAIN-3D" x="277" y="0"></use><use xlink:href="#E8-MJMATHI-4D" x="1333" y="0"></use><use xlink:href="#E8-MJMATHI-61" x="2384" y="0"></use><use xlink:href="#E8-MJMATHI-78" x="2913" y="0"></use><use xlink:href="#E8-MJMAIN-28" x="3485" y="0"></use></g></g><g transform="translate(14124,0)"><use xlink:href="#E8-MJMAIN-2C" x="0" y="650"></use><use xlink:href="#E8-MJMAIN-2C" x="0" y="-700"></use></g><g transform="translate(14402,0)"><g transform="translate(0,650)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-5B" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="828" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="1395" y="0"></use><use xlink:href="#E8-MJMAIN-31" x="2395" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="2895" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="3340" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="3974" y="0"></use><use xlink:href="#E8-MJMATHI-76" x="4974" y="0"></use><use xlink:href="#E8-MJMAIN-5D" x="5459" y="0"></use><use xlink:href="#E8-MJMAIN-2B" x="5959" y="0"></use><use xlink:href="#E8-MJMATHI-77" x="6960" y="0"></use></g><g transform="translate(0,-700)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-5B" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="828" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="1395" y="0"></use><use xlink:href="#E8-MJMAIN-31" x="2395" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="2895" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="3340" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="3974" y="0"></use><use xlink:href="#E8-MJMATHI-76" x="4974" y="0"></use><use xlink:href="#E8-MJMAIN-5D" x="5459" y="0"></use></g></g><g transform="translate(24078,0)"><use xlink:href="#E8-MJMAIN-2C" x="0" y="650"></use><use xlink:href="#E8-MJMAIN-2C" x="0" y="-700"></use></g><g transform="translate(24356,0)"><g transform="translate(0,650)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-5B" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="828" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="1395" y="0"></use><use xlink:href="#E8-MJMAIN-31" x="2395" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="2895" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="3340" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="3974" y="0"></use><use xlink:href="#E8-MJMAIN-32" x="4974" y="0"></use><use xlink:href="#E8-MJMATHI-76" x="5474" y="0"></use><use xlink:href="#E8-MJMAIN-5D" x="5959" y="0"></use><use xlink:href="#E8-MJMAIN-2B" x="6459" y="0"></use><use xlink:href="#E8-MJMAIN-32" x="7460" y="0"></use><use xlink:href="#E8-MJMATHI-77" x="7960" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="8676" y="0"></use></g><g transform="translate(0,-700)"><use xlink:href="#E8-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-5B" x="550" y="0"></use><use xlink:href="#E8-MJMATHI-69" x="828" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="1395" y="0"></use><use xlink:href="#E8-MJMAIN-31" x="2395" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="2895" y="0"></use><use xlink:href="#E8-MJMATHI-6A" x="3340" y="0"></use><use xlink:href="#E8-MJMAIN-2212" x="3974" y="0"></use><use xlink:href="#E8-MJMAIN-32" x="4974" y="0"></use><use xlink:href="#E8-MJMATHI-76" x="5474" y="0"></use><use xlink:href="#E8-MJMAIN-5D" x="5959" y="0"></use><use xlink:href="#E8-MJMAIN-2B" x="6459" y="0"></use><use xlink:href="#E8-MJMATHI-77" x="7460" y="0"></use><use xlink:href="#E8-MJMAIN-2C" x="8176" y="0"></use></g></g><g transform="translate(35310,0)"><g transform="translate(0,650)"><use xlink:href="#E8-MJMAIN-2E" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-2E" x="444" y="0"></use><use xlink:href="#E8-MJMAIN-2E" x="889" y="0"></use><use xlink:href="#E8-MJMAIN-29" x="1334" y="0"></use></g><g transform="translate(0,-700)"><use xlink:href="#E8-MJMAIN-2E" x="0" y="0"></use><use xlink:href="#E8-MJMAIN-2E" x="444" y="0"></use><use xlink:href="#E8-MJMAIN-2E" x="889" y="0"></use><use xlink:href="#E8-MJMAIN-29" x="1334" y="0"></use></g></g></g></g></svg></span></div><script type="math/tex; mode=display" id="MathJax-Element-2">\begin{equation}
\begin{aligned}
	f(i,j) &= Max(f[i-1,j]&, &f[i-1, j-v] + w&, &f[i-1, j-2v] + 2w, &...) \\
	f(i,j-v)&= Max(       &, &f[i-1, j-v]&,     &f[i-1, j-2v] + w,  &...)
\end{aligned}
\end{equation}</script></div></div><p><span>由此可得</span></p><div contenteditable="false" spellcheck="false" class="mathjax-block md-end-block md-math-block md-rawblock" id="mathjax-n54" cid="n54" mdtype="math_block"><div class="md-rawblock-container md-math-container" tabindex="-1"><div class="MathJax_SVG_Display" style="text-align: center;"><span class="MathJax_SVG" id="MathJax-Element-3-Frame" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="39.999ex" height="2.636ex" viewBox="0 -828.3 17221.6 1134.7" role="img" focusable="false" style="vertical-align: -0.712ex; max-width: 100%;"><defs><path stroke-width="0" id="E9-MJMATHI-66" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path stroke-width="0" id="E9-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E9-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E9-MJMAIN-2C" d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z"></path><path stroke-width="0" id="E9-MJMATHI-6A" d="M297 596Q297 627 318 644T361 661Q378 661 389 651T403 623Q403 595 384 576T340 557Q322 557 310 567T297 596ZM288 376Q288 405 262 405Q240 405 220 393T185 362T161 325T144 293L137 279Q135 278 121 278H107Q101 284 101 286T105 299Q126 348 164 391T252 441Q253 441 260 441T272 442Q296 441 316 432Q341 418 354 401T367 348V332L318 133Q267 -67 264 -75Q246 -125 194 -164T75 -204Q25 -204 7 -183T-12 -137Q-12 -110 7 -91T53 -71Q70 -71 82 -81T95 -112Q95 -148 63 -167Q69 -168 77 -168Q111 -168 139 -140T182 -74L193 -32Q204 11 219 72T251 197T278 308T289 365Q289 372 288 376Z"></path><path stroke-width="0" id="E9-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path stroke-width="0" id="E9-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="0" id="E9-MJMATHI-4D" d="M289 629Q289 635 232 637Q208 637 201 638T194 648Q194 649 196 659Q197 662 198 666T199 671T201 676T203 679T207 681T212 683T220 683T232 684Q238 684 262 684T307 683Q386 683 398 683T414 678Q415 674 451 396L487 117L510 154Q534 190 574 254T662 394Q837 673 839 675Q840 676 842 678T846 681L852 683H948Q965 683 988 683T1017 684Q1051 684 1051 673Q1051 668 1048 656T1045 643Q1041 637 1008 637Q968 636 957 634T939 623Q936 618 867 340T797 59Q797 55 798 54T805 50T822 48T855 46H886Q892 37 892 35Q892 19 885 5Q880 0 869 0Q864 0 828 1T736 2Q675 2 644 2T609 1Q592 1 592 11Q592 13 594 25Q598 41 602 43T625 46Q652 46 685 49Q699 52 704 61Q706 65 742 207T813 490T848 631L654 322Q458 10 453 5Q451 4 449 3Q444 0 433 0Q418 0 415 7Q413 11 374 317L335 624L267 354Q200 88 200 79Q206 46 272 46H282Q288 41 289 37T286 19Q282 3 278 1Q274 0 267 0Q265 0 255 0T221 1T157 2Q127 2 95 1T58 0Q43 0 39 2T35 11Q35 13 38 25T43 40Q45 46 65 46Q135 46 154 86Q158 92 223 354T289 629Z"></path><path stroke-width="0" id="E9-MJMATHI-61" d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z"></path><path stroke-width="0" id="E9-MJMATHI-78" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path stroke-width="0" id="E9-MJMAIN-5B" d="M118 -250V750H255V710H158V-210H255V-250H118Z"></path><path stroke-width="0" id="E9-MJMAIN-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path stroke-width="0" id="E9-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="0" id="E9-MJMAIN-5D" d="M22 710V750H159V-250H22V-210H119V710H22Z"></path><path stroke-width="0" id="E9-MJMATHI-76" d="M173 380Q173 405 154 405Q130 405 104 376T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Q21 294 29 316T53 368T97 419T160 441Q202 441 225 417T249 361Q249 344 246 335Q246 329 231 291T200 202T182 113Q182 86 187 69Q200 26 250 26Q287 26 319 60T369 139T398 222T409 277Q409 300 401 317T383 343T365 361T357 383Q357 405 376 424T417 443Q436 443 451 425T467 367Q467 340 455 284T418 159T347 40T241 -11Q177 -11 139 22Q102 54 102 117Q102 148 110 181T151 298Q173 362 173 380Z"></path><path stroke-width="0" id="E9-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="0" id="E9-MJMATHI-77" d="M580 385Q580 406 599 424T641 443Q659 443 674 425T690 368Q690 339 671 253Q656 197 644 161T609 80T554 12T482 -11Q438 -11 404 5T355 48Q354 47 352 44Q311 -11 252 -11Q226 -11 202 -5T155 14T118 53T104 116Q104 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Q21 293 29 315T52 366T96 418T161 441Q204 441 227 416T250 358Q250 340 217 250T184 111Q184 65 205 46T258 26Q301 26 334 87L339 96V119Q339 122 339 128T340 136T341 143T342 152T345 165T348 182T354 206T362 238T373 281Q402 395 406 404Q419 431 449 431Q468 431 475 421T483 402Q483 389 454 274T422 142Q420 131 420 107V100Q420 85 423 71T442 42T487 26Q558 26 600 148Q609 171 620 213T632 273Q632 306 619 325T593 357T580 385Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E9-MJMATHI-66" x="0" y="0"></use><use xlink:href="#E9-MJMAIN-28" x="550" y="0"></use><use xlink:href="#E9-MJMATHI-69" x="939" y="0"></use><use xlink:href="#E9-MJMAIN-2C" x="1284" y="0"></use><use xlink:href="#E9-MJMATHI-6A" x="1728" y="0"></use><use xlink:href="#E9-MJMAIN-29" x="2140" y="0"></use><use xlink:href="#E9-MJMAIN-3D" x="2807" y="0"></use><use xlink:href="#E9-MJMATHI-4D" x="3863" y="0"></use><use xlink:href="#E9-MJMATHI-61" x="4914" y="0"></use><use xlink:href="#E9-MJMATHI-78" x="5443" y="0"></use><use xlink:href="#E9-MJMAIN-28" x="6015" y="0"></use><use xlink:href="#E9-MJMATHI-66" x="6404" y="0"></use><use xlink:href="#E9-MJMAIN-5B" x="6954" y="0"></use><use xlink:href="#E9-MJMATHI-69" x="7232" y="0"></use><use xlink:href="#E9-MJMAIN-2212" x="7799" y="0"></use><use xlink:href="#E9-MJMAIN-31" x="8799" y="0"></use><use xlink:href="#E9-MJMAIN-2C" x="9299" y="0"></use><use xlink:href="#E9-MJMATHI-6A" x="9744" y="0"></use><use xlink:href="#E9-MJMAIN-5D" x="10156" y="0"></use><use xlink:href="#E9-MJMAIN-2C" x="10434" y="0"></use><use xlink:href="#E9-MJMATHI-66" x="10879" y="0"></use><use xlink:href="#E9-MJMAIN-5B" x="11429" y="0"></use><use xlink:href="#E9-MJMATHI-69" x="11707" y="0"></use><use xlink:href="#E9-MJMAIN-2C" x="12052" y="0"></use><use xlink:href="#E9-MJMATHI-6A" x="12496" y="0"></use><use xlink:href="#E9-MJMAIN-2212" x="13130" y="0"></use><use xlink:href="#E9-MJMATHI-76" x="14131" y="0"></use><use xlink:href="#E9-MJMAIN-5D" x="14616" y="0"></use><use xlink:href="#E9-MJMAIN-2B" x="15116" y="0"></use><use xlink:href="#E9-MJMATHI-77" x="16116" y="0"></use><use xlink:href="#E9-MJMAIN-29" x="16832" y="0"></use></g></svg></span></div><script type="math/tex; mode=display" id="MathJax-Element-3">\begin{equation}
	f(i,j) = Max(f[i-1,j],f[i,j-v]+w)
\end{equation}</script></div></div><p><span>从而写出</span><span class="MathJax_SVG" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="6.754ex" height="2.838ex" viewBox="0 -915.3 2908.1 1221.7" role="img" focusable="false" style="vertical-align: -0.712ex;"><defs><path stroke-width="0" id="E6-MJMATHI-4F" d="M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z"></path><path stroke-width="0" id="E6-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E6-MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path><path stroke-width="0" id="E6-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="0" id="E6-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E6-MJMATHI-4F" x="0" y="0"></use><use xlink:href="#E6-MJMAIN-28" x="763" y="0"></use><g transform="translate(1152,0)"><use xlink:href="#E6-MJMATHI-4E" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E6-MJMAIN-32" x="1291" y="513"></use></g><use xlink:href="#E6-MJMAIN-29" x="2519" y="0"></use></g></svg></span><script type="math/tex"> O(N^2) </script><span>的优化版本</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>6</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span> (<span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]) <span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">} &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 173px;"></div><div class="CodeMirror-gutters" style="height: 173px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>最终去掉一维数组，得到最终的空间优化版本</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>3</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation"><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>]; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 86px;"></div><div class="CodeMirror-gutters" style="height: 86px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>因为</span><code>j-v[i]</code><span>一定是小于</span><code>j</code><span>，所以</span><code>f[j-v[i]]</code><span>一定是在</span><code>f[j]</code><span>之前被计算出来，所以等价于</span><code>f[i][j-v[i]]</code></p><p><strong><span>总结</span></strong></p><p><img src="https://pic.downk.cc/item/5f1f8db614195aa59466529b.png" referrerpolicy="no-referrer"></p><p><span>完全背包在进行更新的时候，有可能使用到的 </span><code>f[j-v[i]]</code><span>已经是选择了若干次</span><code>i</code><span>物品的状态了，因为转移是发生在整个第</span><code>i</code><span>层上相同层状态的转移，（选择了一个</span><code>i</code><span>的被选择两个</span><code>i</code><span>的状态更新）。</span></p><h2><a name="多重背包" class="md-header-anchor"></a><span>多重背包</span></h2><p><span>每个物品数量不一样，最多有Si个</span></p><blockquote><p><span>有 N 种物品和一个容量是 V 的背包。</span></p><p><span>第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。</span></p><p><span>求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。</span>
<span>输出最大价值。</span></p></blockquote><p><img src="https://pic.downk.cc/item/5f20f66c14195aa59411216f.jpg" referrerpolicy="no-referrer"></p><p><span>朴素版本的多重背包问题和完全背包非常相似，只是在物体的数量上做出了限制</span></p><p><span>代码如下：</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>6</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) <span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">s</span>[<span class="cm-variable">i</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">k</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">k</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">s</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&amp;&amp;</span> <span class="cm-variable">k</span> <span class="cm-operator">*</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>] <span class="cm-operator">&lt;=</span> <span class="cm-variable">j</span>; <span class="cm-variable">k</span> <span class="cm-operator">++</span>)</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>][<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>]<span class="cm-operator">*</span><span class="cm-variable">k</span>] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>]<span class="cm-operator">*</span><span class="cm-variable">k</span>);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">cout</span> <span class="cm-operator">&lt;&lt;</span> <span class="cm-variable">f</span>[<span class="cm-variable">n</span>][<span class="cm-variable">m</span>] <span class="cm-operator">&lt;&lt;</span> <span class="cm-variable">endl</span>;</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 173px;"></div><div class="CodeMirror-gutters" style="height: 173px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>但是问题也很明显，时间复杂度是</span><span class="MathJax_SVG" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="8.926ex" height="2.636ex" viewBox="0 -828.3 3843 1134.7" role="img" focusable="false" style="vertical-align: -0.712ex;"><defs><path stroke-width="0" id="E7-MJMATHI-4F" d="M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z"></path><path stroke-width="0" id="E7-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E7-MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path><path stroke-width="0" id="E7-MJMATHI-56" d="M52 648Q52 670 65 683H76Q118 680 181 680Q299 680 320 683H330Q336 677 336 674T334 656Q329 641 325 637H304Q282 635 274 635Q245 630 242 620Q242 618 271 369T301 118L374 235Q447 352 520 471T595 594Q599 601 599 609Q599 633 555 637Q537 637 537 648Q537 649 539 661Q542 675 545 679T558 683Q560 683 570 683T604 682T668 681Q737 681 755 683H762Q769 676 769 672Q769 655 760 640Q757 637 743 637Q730 636 719 635T698 630T682 623T670 615T660 608T652 599T645 592L452 282Q272 -9 266 -16Q263 -18 259 -21L241 -22H234Q216 -22 216 -15Q213 -9 177 305Q139 623 138 626Q133 637 76 637H59Q52 642 52 648Z"></path><path stroke-width="0" id="E7-MJMATHI-53" d="M308 24Q367 24 416 76T466 197Q466 260 414 284Q308 311 278 321T236 341Q176 383 176 462Q176 523 208 573T273 648Q302 673 343 688T407 704H418H425Q521 704 564 640Q565 640 577 653T603 682T623 704Q624 704 627 704T632 705Q645 705 645 698T617 577T585 459T569 456Q549 456 549 465Q549 471 550 475Q550 478 551 494T553 520Q553 554 544 579T526 616T501 641Q465 662 419 662Q362 662 313 616T263 510Q263 480 278 458T319 427Q323 425 389 408T456 390Q490 379 522 342T554 242Q554 216 546 186Q541 164 528 137T492 78T426 18T332 -20Q320 -22 298 -22Q199 -22 144 33L134 44L106 13Q83 -14 78 -18T65 -22Q52 -22 52 -14Q52 -11 110 221Q112 227 130 227H143Q149 221 149 216Q149 214 148 207T144 186T142 153Q144 114 160 87T203 47T255 29T308 24Z"></path><path stroke-width="0" id="E7-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E7-MJMATHI-4F" x="0" y="0"></use><use xlink:href="#E7-MJMAIN-28" x="763" y="0"></use><use xlink:href="#E7-MJMATHI-4E" x="1152" y="0"></use><use xlink:href="#E7-MJMATHI-56" x="2040" y="0"></use><use xlink:href="#E7-MJMATHI-53" x="2809" y="0"></use><use xlink:href="#E7-MJMAIN-29" x="3454" y="0"></use></g></svg></span><script type="math/tex"> O(NVS) </script><span>当数据量达到1000的时候就会超时</span></p><p><strong><span>那么，采用和完全背包一样的优化方法可以吗？（不行）</span></strong></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>3</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation"><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">f</span>(<span class="cm-variable">i</span>,<span class="cm-variable">j</span>) &nbsp; <span class="cm-operator">=</span> <span class="cm-variable">Max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>] <span class="cm-operator">+</span> <span class="cm-variable">w</span>, <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-number">2v</span>]<span class="cm-operator">+</span><span class="cm-number">2w</span>,..., <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">sv</span>]<span class="cm-operator">+</span> <span class="cm-variable">sw</span>) </span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">f</span>(<span class="cm-variable">i</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>) <span class="cm-operator">=</span> <span class="cm-variable">Max</span>( &nbsp; &nbsp; &nbsp;  , <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">v</span>] &nbsp;  , <span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-number">2v</span>]<span class="cm-operator">+</span> <span class="cm-variable">w</span>,..., <span class="cm-variable">f</span>[<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">sv</span>]<span class="cm-operator">+</span>(<span class="cm-variable">s</span><span class="cm-operator">-</span><span class="cm-number">1</span>)<span class="cm-variable">w</span>,</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">i</span><span class="cm-operator">-</span><span class="cm-number">1</span>,<span class="cm-variable">j</span><span class="cm-operator">-</span>(<span class="cm-variable">s</span><span class="cm-operator">+</span><span class="cm-number">1</span>)<span class="cm-variable">v</span>]<span class="cm-operator">+</span><span class="cm-variable">sw</span>)</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 86px;"></div><div class="CodeMirror-gutters" style="height: 86px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>因为这次项数是有限的，最后会多出来一项</span><code>f[i-1,j-(s+1)v]+sw</code><span>所以优化失败。</span></p><p><strong><span>这里采用了二进制拆分来进行优化</span></strong></p><p><span>如果一个物体有</span><code>S</code><span>个，正常枚举需要枚举</span><code>S</code><span>次，但是我们可以将其分别打包成为</span><code>log(s)</code><span>组，用这</span><code>log(S)</code><span>组物品可以凑出</span><code>0-S</code><span>中的任何一个数，就成功将其转化为</span><code>01背包</code><span>问题。</span></p><p><span>打包方法</span></p><div contenteditable="false" spellcheck="false" class="mathjax-block md-end-block md-math-block md-rawblock" id="mathjax-n80" cid="n80" mdtype="math_block"><div class="md-rawblock-container md-math-container" tabindex="-1"><div class="MathJax_SVG_Display"><span class="MathJax_SVG" id="MathJax-Element-4-Frame" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="79.899ex" height="10.413ex" viewBox="0 -958.8 34400.8 4483.5" role="img" focusable="false" style="vertical-align: -8.186ex; max-width: 100%;"><defs><path stroke-width="0" id="E10-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="0" id="E10-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="0" id="E10-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="0" id="E10-MJMAIN-34" d="M462 0Q444 3 333 3Q217 3 199 0H190V46H221Q241 46 248 46T265 48T279 53T286 61Q287 63 287 115V165H28V211L179 442Q332 674 334 675Q336 677 355 677H373L379 671V211H471V165H379V114Q379 73 379 66T385 54Q393 47 442 46H471V0H462ZM293 211V545L74 212L183 211H293Z"></path><path stroke-width="0" id="E10-MJMAIN-38" d="M70 417T70 494T124 618T248 666Q319 666 374 624T429 515Q429 485 418 459T392 417T361 389T335 371T324 363L338 354Q352 344 366 334T382 323Q457 264 457 174Q457 95 399 37T249 -22Q159 -22 101 29T43 155Q43 263 172 335L154 348Q133 361 127 368Q70 417 70 494ZM286 386L292 390Q298 394 301 396T311 403T323 413T334 425T345 438T355 454T364 471T369 491T371 513Q371 556 342 586T275 624Q268 625 242 625Q201 625 165 599T128 534Q128 511 141 492T167 463T217 431Q224 426 228 424L286 386ZM250 21Q308 21 350 55T392 137Q392 154 387 169T375 194T353 216T330 234T301 253T274 270Q260 279 244 289T218 306L210 311Q204 311 181 294T133 239T107 157Q107 98 150 60T250 21Z"></path><path stroke-width="0" id="E10-MJMAIN-2E" d="M78 60Q78 84 95 102T138 120Q162 120 180 104T199 61Q199 36 182 18T139 0T96 17T78 60Z"></path><path stroke-width="0" id="E10-MJMATHI-6B" d="M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"></path><path stroke-width="0" id="E10-MJMAIN-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path stroke-width="0" id="E10-MJMATHI-43" d="M50 252Q50 367 117 473T286 641T490 704Q580 704 633 653Q642 643 648 636T656 626L657 623Q660 623 684 649Q691 655 699 663T715 679T725 690L740 705H746Q760 705 760 698Q760 694 728 561Q692 422 692 421Q690 416 687 415T669 413H653Q647 419 647 422Q647 423 648 429T650 449T651 481Q651 552 619 605T510 659Q484 659 454 652T382 628T299 572T226 479Q194 422 175 346T156 222Q156 108 232 58Q280 24 350 24Q441 24 512 92T606 240Q610 253 612 255T628 257Q648 257 648 248Q648 243 647 239Q618 132 523 55T319 -22Q206 -22 128 53T50 252Z"></path><path stroke-width="0" id="E10-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="0" id="E10-MJMATHI-53" d="M308 24Q367 24 416 76T466 197Q466 260 414 284Q308 311 278 321T236 341Q176 383 176 462Q176 523 208 573T273 648Q302 673 343 688T407 704H418H425Q521 704 564 640Q565 640 577 653T603 682T623 704Q624 704 627 704T632 705Q645 705 645 698T617 577T585 459T569 456Q549 456 549 465Q549 471 550 475Q550 478 551 494T553 520Q553 554 544 579T526 616T501 641Q465 662 419 662Q362 662 313 616T263 510Q263 480 278 458T319 427Q323 425 389 408T456 390Q490 379 522 342T554 242Q554 216 546 186Q541 164 528 137T492 78T426 18T332 -20Q320 -22 298 -22Q199 -22 144 33L134 44L106 13Q83 -14 78 -18T65 -22Q52 -22 52 -14Q52 -11 110 221Q112 227 130 227H143Q149 221 149 216Q149 214 148 207T144 186T142 153Q144 114 160 87T203 47T255 29T308 24Z"></path><path stroke-width="0" id="E10-MJMAIN-3C" d="M694 -11T694 -19T688 -33T678 -40Q671 -40 524 29T234 166L90 235Q83 240 83 250Q83 261 91 266Q664 540 678 540Q681 540 687 534T694 519T687 505Q686 504 417 376L151 250L417 124Q686 -4 687 -5Q694 -11 694 -19Z"></path><path stroke-width="0" id="E10-MJSZ2-2211" d="M60 948Q63 950 665 950H1267L1325 815Q1384 677 1388 669H1348L1341 683Q1320 724 1285 761Q1235 809 1174 838T1033 881T882 898T699 902H574H543H251L259 891Q722 258 724 252Q725 250 724 246Q721 243 460 -56L196 -356Q196 -357 407 -357Q459 -357 548 -357T676 -358Q812 -358 896 -353T1063 -332T1204 -283T1307 -196Q1328 -170 1348 -124H1388Q1388 -125 1381 -145T1356 -210T1325 -294L1267 -449L666 -450Q64 -450 61 -448Q55 -446 55 -439Q55 -437 57 -433L590 177Q590 178 557 222T452 366T322 544L56 909L55 924Q55 945 60 948Z"></path><path stroke-width="0" id="E10-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E10-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path stroke-width="0" id="E10-MJMAIN-2264" d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(8909,0)"><use xlink:href="#E10-MJMAIN-31" x="0" y="0"></use><use xlink:href="#E10-MJMAIN-2B" x="722" y="0"></use><use xlink:href="#E10-MJMAIN-32" x="1722" y="0"></use><use xlink:href="#E10-MJMAIN-2B" x="2444" y="0"></use><use xlink:href="#E10-MJMAIN-34" x="3444" y="0"></use><use xlink:href="#E10-MJMAIN-2B" x="4167" y="0"></use><use xlink:href="#E10-MJMAIN-38" x="5167" y="0"></use><use xlink:href="#E10-MJMAIN-2B" x="5667" y="0"></use><use xlink:href="#E10-MJMAIN-2E" x="6445" y="0"></use><use xlink:href="#E10-MJMAIN-2E" x="6890" y="0"></use><use xlink:href="#E10-MJMAIN-2E" x="7334" y="0"></use><use xlink:href="#E10-MJMAIN-2B" x="7779" y="0"></use><g transform="translate(8557,0)"><use xlink:href="#E10-MJMAIN-32" x="0" y="0"></use><g transform="translate(500,412)"><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-6B" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-2212" x="521" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-31" x="1299" y="0"></use></g></g><use xlink:href="#E10-MJMAIN-2B" x="10651" y="0"></use><g transform="translate(11651,0)"><use xlink:href="#E10-MJMAIN-32" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-6B" x="707" y="583"></use></g><use xlink:href="#E10-MJMAIN-2B" x="12842" y="0"></use><use xlink:href="#E10-MJMATHI-43" x="13842" y="0"></use><use xlink:href="#E10-MJMAIN-3D" x="14880" y="0"></use><use xlink:href="#E10-MJMATHI-53" x="15936" y="0"></use></g><g transform="translate(11243,-2254)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(43.49) matrix(1 0 0 -1 0 0)">其</text><g transform="translate(782,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(43.49) matrix(1 0 0 -1 0 0)">中</text></g><g transform="translate(1565,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(43.49) matrix(1 0 0 -1 0 0)">，</text></g><use xlink:href="#E10-MJMATHI-43" x="2348" y="0"></use><use xlink:href="#E10-MJMAIN-3C" x="3386" y="0"></use><g transform="translate(4442,0)"><use xlink:href="#E10-MJMAIN-32" x="0" y="0"></use><g transform="translate(500,412)"><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-6B" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-2B" x="521" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-31" x="1299" y="0"></use></g></g><g transform="translate(7480,0)"><use xlink:href="#E10-MJSZ2-2211" x="0" y="0"></use><g transform="translate(148,-1088)"><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-3D" x="345" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMAIN-30" x="1123" y="0"></use></g><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-6B" x="760" y="1626"></use></g><g transform="translate(9091,0)"><use xlink:href="#E10-MJMAIN-32" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E10-MJMATHI-69" x="707" y="583"></use></g><use xlink:href="#E10-MJMAIN-2264" x="10213" y="0"></use><use xlink:href="#E10-MJMATHI-53" x="11268" y="0"></use></g></g></svg></span></div><script type="math/tex; mode=display" id="MathJax-Element-4">\begin{equation}
	1 + 2 + 4 + 8 + ... +2^{k-1}+2^k+C = S \\
	其中，C < 2^{k+1}\quad  \sum_{i=0}^{k}{2^{i}} \leq S
\end{equation}</script></div></div><p><span>例子:</span></p><p><img src="https://pic.downk.cc/item/5f2138d014195aa59456453b.jpg" referrerpolicy="no-referrer"></p><p><span>那么从</span><code>0-21</code><span>中的选择就转化为在这5个数中，选或者不选的</span><code>01背包问题</code><span>了。</span></p><p><strong><span>优化步骤：</span></strong></p><ul><li><span>将每个物品的数量</span><code>Si</code><span>进行二进制拆分为</span><code>logS</code><span>个物体</span></li><li><span>计算分组后的新体积和价值</span></li><li><span>用</span><code>01背包</code><span>进行计算</span></li></ul><p><strong><span>代码</span></strong></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>31</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;bits/stdc++.h&gt;</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">using</span> <span class="cm-keyword">namespace</span> <span class="cm-def">std</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">const</span> <span class="cm-variable-3">int</span> <span class="cm-variable">N</span> <span class="cm-operator">=</span> <span class="cm-number">2020</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-variable">n</span>, <span class="cm-variable">m</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-variable">f</span>[<span class="cm-variable">N</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">7</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">8</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">struct</span> <span class="cm-def">good</span> {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">9</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable-3">int</span> <span class="cm-variable">v</span>, <span class="cm-variable">w</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">10</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">};</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">11</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">12</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">vector</span><span class="cm-operator">&lt;</span><span class="cm-variable">good</span><span class="cm-operator">&gt;</span> <span class="cm-variable">goods</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">13</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">14</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable-3">int</span> <span class="cm-def">main</span>() {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">15</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">n</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">m</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">16</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">17</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable-3">int</span> <span class="cm-variable">v</span>, <span class="cm-variable">w</span>, <span class="cm-variable">s</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">18</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">v</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">w</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">s</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">19</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">k</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">k</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">s</span>; <span class="cm-variable">k</span> <span class="cm-operator">&lt;&lt;=</span> <span class="cm-number">1</span>) {</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">20</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">s</span> <span class="cm-operator">-=</span> <span class="cm-variable">k</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">21</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">goods</span>.<span class="cm-variable">push_back</span>({<span class="cm-variable">k</span><span class="cm-operator">*</span><span class="cm-variable">v</span>, <span class="cm-variable">k</span><span class="cm-operator">*</span><span class="cm-variable">w</span>});</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">22</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">23</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span> (<span class="cm-variable">s</span> <span class="cm-operator">&gt;</span> <span class="cm-number">0</span>) <span class="cm-variable">goods</span>.<span class="cm-variable">push_back</span>({<span class="cm-variable">s</span><span class="cm-operator">*</span><span class="cm-variable">v</span>, <span class="cm-variable">s</span><span class="cm-operator">*</span><span class="cm-variable">w</span>});</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">24</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  }</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">25</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">26</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-keyword">auto</span> <span class="cm-variable">good</span>: <span class="cm-variable">goods</span>) </span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">27</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">good</span>.<span class="cm-variable">v</span>; <span class="cm-variable">j</span> <span class="cm-operator">--</span>) </span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">28</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span><span class="cm-operator">-</span><span class="cm-variable">good</span>.<span class="cm-variable">v</span>] <span class="cm-operator">+</span> <span class="cm-variable">good</span>.<span class="cm-variable">w</span>);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">29</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">cout</span> <span class="cm-operator">&lt;&lt;</span> <span class="cm-variable">f</span>[<span class="cm-variable">m</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">30</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">return</span> <span class="cm-number">0</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">31</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 893px;"></div><div class="CodeMirror-gutters" style="height: 893px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><h2><a name="分组背包" class="md-header-anchor"></a><span>分组背包</span></h2><p><span>物品分为若干种，每一组里面最多只能选择一个物品，是互斥的。</span></p><p><img src="https://pic.downk.cc/item/5f21450214195aa59460aa38.jpg" referrerpolicy="no-referrer"></p><p><strong><span>多重背包是枚举第i件物品选几个，分组背包是枚举第i组物品选哪个</span></strong></p><p><span>就是在每组里面跑</span><code>01背包</code></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>12</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span> ){</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">s</span>[<span class="cm-variable">i</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">j</span> <span class="cm-operator">&lt;</span> <span class="cm-variable">s</span>[<span class="cm-variable">i</span>]; <span class="cm-variable">j</span> <span class="cm-operator">++</span> )</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">cin</span> <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>] <span class="cm-operator">&gt;&gt;</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>][<span class="cm-variable">j</span>];</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="">​</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">7</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">n</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span> )</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">8</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-number">0</span>; <span class="cm-variable">j</span> <span class="cm-operator">--</span> ) <span class="cm-comment">// n组物品跑01背包</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">9</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span> (<span class="cm-variable-3">int</span> <span class="cm-variable">k</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>; <span class="cm-variable">k</span> <span class="cm-operator">&lt;</span> <span class="cm-variable">s</span>[<span class="cm-variable">i</span>]; <span class="cm-variable">k</span> <span class="cm-operator">++</span> ) <span class="cm-comment">// 枚举组内物品，选一个最大的</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">10</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span> (<span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>][<span class="cm-variable">k</span>])</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">11</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span> <span class="cm-operator">-</span> <span class="cm-variable">v</span>[<span class="cm-variable">i</span>][<span class="cm-variable">k</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">i</span>][<span class="cm-variable">k</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">12</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">printf</span>(<span class="cm-string">"%d"</span>, <span class="cm-variable">f</span>[<span class="cm-variable">m</span>]);</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 346px;"></div><div class="CodeMirror-gutters" style="height: 346px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p><span>还有更加清奇的写法（对上面的写法进行</span><strong><span>等价变形</span></strong><span>）</span></p><pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="c++"><div class="CodeMirror cm-s-inner CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9px; left: 49px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 36px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre><div class="CodeMirror-linenumber CodeMirror-gutter-elt"><div>10</div></div></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: -36px; width: 36px;"></div><div class="CodeMirror-gutter-wrapper CodeMirror-activeline-gutter" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">1</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">while</span>(<span class="cm-variable">n</span> <span class="cm-operator">--</span>) &nbsp;<span class="cm-comment">// n组物品</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">2</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">{</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">3</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable-3">int</span> <span class="cm-variable">s</span>;</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">4</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">scanf</span>(<span class="cm-string">"%d"</span>, <span class="cm-operator">&amp;</span><span class="cm-variable">s</span>);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">5</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span>(<span class="cm-variable-3">int</span> <span class="cm-variable">i</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">i</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">s</span>; <span class="cm-variable">i</span> <span class="cm-operator">++</span>) &nbsp;<span class="cm-variable">scanf</span>(<span class="cm-string">"%d%d"</span>, <span class="cm-operator">&amp;</span><span class="cm-variable">v</span>[<span class="cm-variable">i</span>], <span class="cm-operator">&amp;</span><span class="cm-variable">w</span>[<span class="cm-variable">i</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">6</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">for</span>(<span class="cm-variable-3">int</span> <span class="cm-variable">j</span> <span class="cm-operator">=</span> <span class="cm-variable">m</span>; <span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-number">0</span>; <span class="cm-variable">j</span> <span class="cm-operator">--</span>) <span class="cm-comment">// 跑01背包</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">7</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">for</span>(<span class="cm-variable-3">int</span> <span class="cm-variable">k</span> <span class="cm-operator">=</span> <span class="cm-number">1</span>; <span class="cm-variable">k</span> <span class="cm-operator">&lt;=</span> <span class="cm-variable">s</span>; <span class="cm-variable">k</span> <span class="cm-operator">++</span>) <span class="cm-comment">// 枚举 k</span></span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">8</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-keyword">if</span>(<span class="cm-variable">j</span> <span class="cm-operator">&gt;=</span> <span class="cm-variable">v</span>[<span class="cm-variable">k</span>]) &nbsp;<span class="cm-variable">f</span>[<span class="cm-variable">j</span>] <span class="cm-operator">=</span> <span class="cm-variable">max</span>(<span class="cm-variable">f</span>[<span class="cm-variable">j</span>], <span class="cm-variable">f</span>[<span class="cm-variable">j</span> <span class="cm-operator">-</span> <span class="cm-variable">v</span>[<span class="cm-variable">k</span>]] <span class="cm-operator">+</span> <span class="cm-variable">w</span>[<span class="cm-variable">k</span>]);</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt" style="left: 0px; width: 37px;">9</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div><div style="position: relative;"><div class="CodeMirror-gutter-wrapper" style="left: -36px;"><div class="CodeMirror-linenumber CodeMirror-gutter-elt CodeMirror-linenumber-show" style="left: 0px; width: 37px;">10</div></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">printf</span>(<span class="cm-string">"%d"</span>, <span class="cm-variable">f</span>[<span class="cm-variable">m</span>]);</span></pre></div></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 288px;"></div><div class="CodeMirror-gutters" style="height: 288px;"><div class="CodeMirror-gutter CodeMirror-linenumbers" style="width: 45px;"></div></div></div></div></pre><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p></div>
</body>
</html>